It looks good. The level of comments definitely needs a bump to make Doxygen happy.

src/sim/addrtrie.hh (Diff revision 1)

const std::string& title?

Show all issues

1. Gabe Black April 9, 2012, 4:29 p.m. (April 9, 2012, 4:29 p.m.)

   Nah. If I did that, it would construct and destruct an object which just wraps the parameter anyway. If I manipulated it that might be a good idea.

Seems fine overall, although I would think it would best be in src/base not src/sim. I second Andreas' comments about Doxygen.

Looks basically ok.  I'd prefer to see this merged with the unit test and the x86 TLB patch and committed as a single changeset.

src/sim/addrtrie.hh (Diff revision 1)

What about templating on the key type too (Addr)?  Then it would be a totally generic trie and should definitely go in base and not sim.

Show all issues

1. Gabe Black April 9, 2012, 4:35 p.m. (April 9, 2012, 4:35 p.m.)

   It would be slightly more generic, but really you'd just be able to change the size of the integer key. It wouldn't work with, for instance, a string key, or if you wanted the most specific match like for IP routing, etc. I'll do it anyway since it's not a totally unreasonable thing to do, and someone may make it more genuinely generic in the future.

2. Steve Reinhardt April 10, 2012, 5:12 a.m. (April 10, 2012, 5:12 a.m.)

   Just because something's a template parameter doesn't mean you can bang in any old type... even the ability to use different width integers seems reasonable (if say there's some reason to want a 32-bit and a 64-bit version in the same code).  There should probably be a comment at the top mentioning that Key should be an integer type.

src/sim/addrtrie.hh (Diff revision 1)

Not sure if the official style guide says anything, but my gut (and I think emacs) would line up the two goesAfter() calls, not offset them by one space.

Show all issues

1. Gabe Black April 9, 2012, 4:35 p.m. (April 9, 2012, 4:35 p.m.)

   This is because it's on the next line, and I think my editor automatically indented it two stops/eight spaces. That happens to almost but not quite line up with the line above. I don't care greatly which way it's done, so I'll line it up.

2. Steve Reinhardt April 10, 2012, 5:12 a.m. (April 10, 2012, 5:12 a.m.)

   Thanks.

src/sim/addrtrie.hh (Diff revision 1)

I don't see what you gain by separating lookup() and lookupNode(), since the latter is only called from the former, and the separation requires an extra check of node for being non-null.

Show all issues

1. Gabe Black April 9, 2012, 4:35 p.m. (April 9, 2012, 4:35 p.m.)

   If you don't record the Node pointer when you insert something, you need a way to get at it later so you can delete that mapping. Otherwise there's no way to retrieve the Node, just the value it contains. I'm pretty sure the compiler will inline one into the other anyway and be able to get rid of the NULL check.

2. Steve Reinhardt April 10, 2012, 5:12 a.m. (April 10, 2012, 5:12 a.m.)

   That's sort of what I figured was going on initially, except that remove() never calls lookupNode(), so I thought it was pointless... but now I see from the X86 patch that lookupNode() is part of the external interface.  That seems a bit undesirable; I would think that ideally the Node class would not be visible outside the trie.  Can we define an interface that makes that true?
   
   I think if you rewrite TLB::demapPage() as
   
   TlbEntry *entry = trie.lookup(va);
   if (entry) {
      trie.remove(entry->trieNode);
      entry->trieNode = NULL;
      freeList.push_back(entry);
   }
   
   then there would be no need for lookupNode() in the external interface (or as a separate function at all), and no point in the X86 code where you dereference a Node*.  Then the Node class itself could be private, and Node* could be an opaque handle type.
   
   That said, it makes me wonder how much faster the trie is than a hash_map... have you looked at that?

3. Steve Reinhardt April 10, 2012, 7:42 a.m. (April 10, 2012, 7:42 a.m.)

   Oh, but you're using the trie to manage matches on different page sizes, right?  Forgot about that.  Never mind.

src/sim/addrtrie.hh (Diff revision 1)

i.e., just return node->value here instead of node and be done with it...

Nice!  Thanks.  My only comment is that it still seems strange to have lookupHandle() in the public interface, particularly so now that it's not used anywhere in the x86 TLB code.

[Aside: another reason to have the x86 TLB code folded in to the same patch... so we can more easily see how the trie code is supposed to be used at the same time we're reviewing it!  ;-) not trying to start an argument, just couldn't resist making the point...]

I can see where if someone wanted to use the trie but didn't want to bother tracking all the handles themselves, then you might think you'd need this.  However, the only thing a user can do with a handle is call remove on it, so I'd advocate for making an overloaded remove(Key key) method like this:

   Handle h = lookupHandle(key);
   if (h) remove(h);

You could even return a bool if you think the caller will ever care whether something actually got removed or not.

Then lookupHandle() could be made protected, and you have a nice clean public interface that's basically just insert/lookup/remove, and the whole Handle thing is just an optimization to avoid an extra lookup by allowing users to call remove(Handle) instead of remove(Key).  And people reading your code don't have to wonder why you've bothered to factor lookupHandle() out of lookup() even though no one else ever calls it...

src/base/trie.hh (Diff revisions 2 - 3)

I think you mean Handle here (and elsewhere in this comment).

Ship It!