Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
7671034:
doubly-linked free-lists for thread caches and page heaps (Closed)
|
Created:
9 years, 4 months ago by bxx Modified:
7 years, 2 months ago CC:
chromium-reviews, brettw-cc_chromium.org, antonm, willchan no longer on Chromium Visibility:
Public. |
Descriptiontcmalloc doubly-linked free-lists for thread caches
Added the ability for free lists to be built out of doubly-linked lists in tcalloc. TCMALLOC_USE_DOUBLYLINKED_FREELIST flag must be set in order for doubly-linked lists to be used. By default flag is only set in Debug builds.
BUG=None
TEST=None
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=99515
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=100074
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=100525
Patch Set 1 : added #include that was accidently removed #Patch Set 2 : code style fixes #
Total comments: 77
Patch Set 3 : style tweaks, fixed pointer checks, reduce wasted space #Patch Set 4 : add doubly linked lists to page_heap_allocator #
Total comments: 10
Patch Set 5 : clean up code, improve macro name #
Total comments: 30
Patch Set 6 : fix macros and size class checks #
Total comments: 14
Patch Set 7 : added references to SLL_* functions #
Total comments: 2
Patch Set 8 : move size implementation #
Total comments: 4
Patch Set 9 : add check in size #Patch Set 10 : size assert->memory check #Patch Set 11 : fix FL interface, class sizes #Patch Set 12 : change macro name #Patch Set 13 : remove macros #Patch Set 14 : nit fixes #Patch Set 15 : remove inline to fix linking problems #Patch Set 16 : enable doubly linked lists only in Debug builds #Messages
Total messages: 27 (0 generated)
+cc antonm and willchan, as they are picky enough to spot stuff to. I'm really psyched about adding this redundancy to linked lists. I'm very hopeful it will not be a big perf hit, and will help us catch malloc-heap-corruption bugs a lot sooner. I spent a lot of time on this review during the week, in part because I think it can help our code-yellow. I'm psyched... and I hope you are too. I have lots of comments, but I thought it was a lot of nice work. As a intern/noogler, you'll have to expect a lot of comments in code. In this case, the code is sooooo critical, it really got a detailed look. The high level comments are: a) Try to make minimalist changes. The goal is to facilitate diffs. b) Fixing unrelated style guide issues should be avoided. This code predates a lot of that, and we don't want extra changes. When in Rome, do as the Romans do... and don't try to change 'em ;-). Architecturally: In the linked list code, decide what you want to check, and stick with exactly that set. I'd suggest validating the ends of the list whenever you push or pop. Don't traverse the list any farther than you need to do that validation. When you do have to traverse a list, validate as you traverse (such as when extracting ranges). IN some places you were performing the same check about 4 times in a row in debug mode, and in other places you missed an end-of-list validation (of a NULL). Constantly think about any semantic changes you induce, and any potentially perf changes. You are IMO messing with *beautiful* and highly evolved code. Try to figure out why they did things one way... and be sure your change fits with that pattern. Hopefully the comments are clear enough. Thanks, Jim http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/central_freelist.cc (left): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:97: for (void* p = span->objects; p != NULL; p = *((void**) p)) { Minimalist changes are better. Merging etc. is easier. Style should comply with surrounding code. You could have merely written: for (void* p = span->objects; p != NULL; p = FL_NEXT(p))) { http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/central_freelist.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:239: tail = FetchFromSpansSafe(); // makes freelist and returns pointer to start Minimalst: Comment here is not critical, and adds to diff. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:253: nit: Remove extra line. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:316: span->objects = NULL; This might be a tad more readable (and connect with the while loop action in line 318) if it were: *tail = NULL; (see next comment about changing its name). This should probably be another macro or function. Perhaps something like: FL_InitList(tail); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:318: tcmalloc::FL_Push(tail, static_cast<void*>(ptr)); I think the change is ok, but it is good to note that you changed the semantics, and now we create a list with the reverse order. The word "tail" is especially deceptive. I really think you have to change it to something like "list" to make this readable (even if it does touch line 311.. and hurt my minimalist mantra). Perf is slightly degraded(?), as we touch (update) span->objects in each iteration. This could (for example) cause a cache line conflict. Truth is, we just did a super-slow OS call... so perhaps it is in the noise... but you *could* form the list with only a local pointer pointing at it, and then (in line 325) make the only setting change to span->objects. That might(?) be more in line with the current code. nit: remove "tcmalloc::" Also, I'd rather stick with reinterpret_cast<> in all places throughout, rather than changing to static_cast<>. This copies the surrounding style, and prevents the reader form thinking there is something subtle afoot. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:323: span->refcount = 0; // No sub-object in use yet Minimalist: Don't correct with today's style. Leave it as one space. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/common.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.cc:165: if (sc > FIRST_SIZE_CLASS && size <= class_to_size_[sc-1]) { The name seems bad, since it is actually the first usable, and not the first size class (unless the code is changed much more). Perhaps: FIRST_USABLE_SIZE_CLASS For completeness, you may as well add something to test the low values, such as: if (AVOID_8_BYTE_CLASSES && (sc == FIRST_USABLE_SIZE_CLASS) == (size <= 16)) CRASH(...) Then again.. they didn't have tests for this... so it is your call. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/common.h (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:34: nit: remove trailing whitespace. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:39: nit: remove extra newline. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:163: // 1 (1 + 7) / 8 1 Note that they were distinguishing a class 0 for 0 length allocations, vs a class 1 for 8 byte allocations. There are some subtlies in malloc about whether we return a null pointer for a requested zero length allocation, vs a unique pointer. I *think* tcmalloc goes with the standard of a unique pointer... so I'm not sure why they distinguish this way... but you should be careful to watch for checking where they might have optionally tried to support the other (NULL return) standard, and can't (with the changes you made here). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:182: return (size_class < MIN_SIZE_CLASS) ? MIN_SIZE_CLASS : size_class; I assume this was added to preclude 8 byte allocations on a 64bit architecture. As written, it adds a perf(?) hit near what looks to be highly optimized code. My guess is that this was written expecting (hoping) to be inlined and they wanted to stay really short and sweet. I like that you avoided broader changes (minimalist!), but perhaps it could be written so that an optimizer could remove it when not active. Note that s and the return value are both signed ints, so it is (I think) hard to tell when the compiler needn't bother. Suggest you change line 182 to something like: if (!AVOID_8_BYTE_CLASSES || size > 8) return size_class; return 2; // The smallest class that needs more than 8 bytes. That would allow the compiler to discard the comparison unless the macro was set, and would have the fast-path(?) for the common case of returning size class directly. I don't really know if this is perf critical... but it sure (to me) looks a bit hand-tuned... and it is nice to have zero impact (guaranteed) when we are not doing this twiddling. We know we have some perf impact when we are active (more broadly)... and we can tune that case better if need be in the future. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:51: return *(reinterpret_cast<void**> (static_cast<void **>(t) + 1)); I suspect (not sure) this code would be a lot cleaner if you defined a struct, and routinely cast to pointer to that struct for manipulation. struct Node { Node* next; Node* prev; }; You might even have helper functions: void* VoidPointer(Node*); Node* NodePointer(void*); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:65: ASSERT(FL_Next_No_Check(previous) == t); I would expect these to be places where we validate memory, and crash otherwise. Why are you just doing a debug check? I think you should have two kinds of getters. One that does the check, and one that doesn't. With the current code, many checks are repeated 3-5 times in debug, and sometimes, you miss a check in release mode. Since you are really hardening this, I'd suggest that the first pass create code that does all the critical checking exactly once (per push or pop operation). If you decide you want more (in Debug?), then add that on top. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:72: ASSERT(FL_Previous_No_Check(next) == t); Again, this this should IMO definitely be MEMORY_CHECK(), and not merely a debug assertion. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:77: *(reinterpret_cast<void**> (static_cast<void **>(t) + 1)) = n; I don't think the second cast (on the left) is needed. You should probably standardize on reinterpret_cast<>, and also it would be much better to have a struct, and not have to do explicit pointer arithmetic (re: ".. + 1"). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:93: // will point to the new head of the linked list. nit: use 80 characters of width so you don't need so many lines. Please do this throughout the file. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:96: if (old == NULL) { // build singleton list nit: Comments should start with caps, be a complete sentence, and end with a period. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:99: if (FL_Next(old)) This is going deeper into the list than any pointers we really need to depend on or touch, so I don't know that you want to go there. You end up wondering where you should stop. IMO, you should keep it to a minimum. This means you should note every redundant value (back pointer) you set as the list takes possession of the data, and be sure you check it (once) as it releases the data. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:100: MEMORY_CHECK(FL_Previous(FL_Next(old)), old); At best, you should use the *_No_Check versions in all MEMORY_CHECK() calls, as the above repeats the same test effectively three times (currently in debug mode). Additionally, line 99 does this test also in debug mode (making a total of 4 runs). I think the test that was needed here and is missing is: MEMORY_CHECK(FL_Prev_No_Check(old), NULL); That ensures that the element that leads the list has not been placed into another list since being pushed. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:113: void *result = *list; Here again I'd suggest the test: MEMORY_CHECK(FL_Prev_No_Check(result), NULL); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:114: if (result && FL_Next(result)) // pointer sanity check result is always non-null (unless we make a mistake in a pop). In fact, if result is null, then line 117 would segv. Line 117 would then be clearer on this point if it read: *list = FL_Next(result); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:115: MEMORY_CHECK(FL_Previous(FL_Next(result)), result); Again, the above does this same test for 3 times (plus one in line 114) in debug. I think you should instead rely on line 117, which currently does this test a 5th time, and make sure it does the test in non-debug mode. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:139: tmp = FL_Next(tmp); This code is definitely a place to do validation, and that is why I thought that Fl_Next() should be doing it in non-debug mode. The cost is nothing, since we're reading the other field of each block (cache lines should load both addresses all the time). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:146: MEMORY_CHECK(FL_Previous(FL_Next(*head)), *head); This is again going one step too far in the checking, as we have no dependency on the next of the head. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:147: FL_SetPrevious(*head, NULL); This is seemingly a bug. We don't need to condition it on head having a next value (as tested in line 145). We need to always set prev to NULL at the start of the list. I'd suggest deleting line 146, and removing the condition FL_Next(*head) from line 145. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:157: if (!start) return; I'd suggest either asserting that end is NULL, or else not bothering to set it on line 132. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:161: MEMORY_CHECK(FL_Previous(FL_Next(start)), start); I have mixed feelings about whether that test is critical... but I'm ok with it. What you left out that is IMO significant is that MEMORY_CHECK(FL_Previous_No_Check(start), NULL); Perhaps you don't care about that pointer (at the start of the list, but IMO, it is good to keep this whole structure clean. If you want to leave it dangling, you really need to say so up front (define the expected conditions at the ends of the list). Line 65 suggested to me that the data is always either valid, or NULL. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:163: MEMORY_CHECK(FL_Next(FL_Previous(end)), end); I'd also vote for a check here: ASSERT(FL_Next_No_Check(end) == NULL); You set it on line 143, but I had a hard time spotting it, and assertion would make it easier (for me) to see correctness. I'm fine for using assertions while we pass data between your methods, and using the MEMORY_CHECK() when we get data back after having it out in circulation (potentially getting overwritten) for any period of time. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:170: FL_SetPrevious(*head, end); Again I'd like to first see a: MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.h:40: // this generally means that each node needs at least 16 byes. The next On a 32 bit platform, you don't need anything more than 8 bytes to hold two pointers. On a 64 bit machine, this will require 16 bytes (as you noted). It would probably be nice if you used that fact to reduce the amount of change (i.e., continued to support classes with an 8 byte size on 32 bit architectures). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.h:59: #define MIN_SIZE_CLASS 2 This should really depend on 64 vs 32 bit architectures. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.h:108: *end = NULL; It is not a big deal... but this assignment to *end seems useless. I only noticed it reading the changed code. When start is null, the end value is never consulted (see line 124). In addition, I *think* we never pop a range of 0 items, so this whole block may be wasteful (and at best should be coded as the uncommon path). It could have a debug assertion... and I'm trying to check on use cases in chrome, but perhaps in google3 it is used in more scenarios. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/tcmalloc.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/tcmalloc.cc:91: nit: don't add extra line. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/thread_cache.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.cc:156: // Pop the top of the list and add the rest to the freelist nit: This file they do use periods at the end of the sentences, you should too. I'd also expand on the comment: Pop the top of the list to return, and add the rest to the freelist. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.cc:157: void *next = start; Perhaps a better name than |next| would be |second|. The code is perfect, but I had to read it a few times to be sure I understood it... and I'm *guessing* the name didn't help. (or it could be I was tired... or worse). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/thread_cache.h (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.h:45: #include "common.h" // for SizeMap, kMaxSize, etc minimalist: don't reorder includes. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.h:47: #include "internal_logging.h" // for ASSERT, etc again... don't reorder. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.h:206: delete extra line.
I made most of the changes you asked for. One of the changes I didn't make was to create a struct for accessing the node pointers-- I realize the original implementation of free lists is very simple, but implementing the lists this way seems different enough for me to point this out. Especially when we are putting a lot of work into minimalistic changes and consistent styling. In my comments I voiced some of my worries of doing some the of the NULL pointer checks you requested. Although the checks don't seem to be a problem, there was nothing in the original implementation that required pushed/popped ranges to be stand-alone lists with the proper NULL pointers set. I also tossed on a small patch that implements doubly linked lists on the page heap allocator. Justin thought it would be better if I add it to this changeset. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/central_freelist.cc (left): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:97: for (void* p = span->objects; p != NULL; p = *((void**) p)) { On 2011/08/20 02:40:30, jar wrote: > Minimalist changes are better. Merging etc. is easier. Style should comply with > surrounding code. > > You could have merely written: > > for (void* p = span->objects; p != NULL; p = FL_NEXT(p))) { Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/central_freelist.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:239: tail = FetchFromSpansSafe(); // makes freelist and returns pointer to start On 2011/08/20 02:40:30, jar wrote: > Minimalst: Comment here is not critical, and adds to diff. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:253: On 2011/08/20 02:40:30, jar wrote: > nit: Remove extra line. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:316: span->objects = NULL; On 2011/08/20 02:40:30, jar wrote: > This might be a tad more readable (and connect with the while loop action in > line 318) if it were: > *tail = NULL; > > (see next comment about changing its name). > > This should probably be another macro or function. Perhaps something like: > FL_InitList(tail); Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:318: tcmalloc::FL_Push(tail, static_cast<void*>(ptr)); I think I fixed it properly. Just to make sure I understand the perf-related issue: what I am reading from this is that perf-related issues may stem from the fact that span->objects is not located on the stack and that this point we are mostly operating on stack variables. Is this approximately the right idea? On 2011/08/20 02:40:30, jar wrote: > I think the change is ok, but it is good to note that you changed the semantics, > and now we create a list with the reverse order. The word "tail" is especially > deceptive. I really think you have to change it to something like "list" to > make this readable (even if it does touch line 311.. and hurt my minimalist > mantra). > > Perf is slightly degraded(?), as we touch (update) span->objects in each > iteration. This could (for example) cause a cache line conflict. Truth is, we > just did a super-slow OS call... so perhaps it is in the noise... but you > *could* form the list with only a local pointer pointing at it, and then (in > line 325) make the only setting change to span->objects. That might(?) be more > in line with the current code. > > nit: remove "tcmalloc::" > > Also, I'd rather stick with reinterpret_cast<> in all places throughout, rather > than changing to static_cast<>. This copies the surrounding style, and prevents > the reader form thinking there is something subtle afoot. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/central_freelist.cc:323: span->refcount = 0; // No sub-object in use yet On 2011/08/20 02:40:30, jar wrote: > Minimalist: Don't correct with today's style. Leave it as one space. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/common.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.cc:165: if (sc > FIRST_SIZE_CLASS && size <= class_to_size_[sc-1]) { On 2011/08/20 02:40:30, jar wrote: > The name seems bad, since it is actually the first usable, and not the first > size class (unless the code is changed much more). > > Perhaps: > FIRST_USABLE_SIZE_CLASS > > For completeness, you may as well add something to test the low values, such as: > if (AVOID_8_BYTE_CLASSES && > (sc == FIRST_USABLE_SIZE_CLASS) == (size <= 16)) > CRASH(...) > > Then again.. they didn't have tests for this... so it is your call. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/common.h (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:34: On 2011/08/20 02:40:30, jar wrote: > nit: remove trailing whitespace. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:39: On 2011/08/20 02:40:30, jar wrote: > nit: remove extra newline. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:163: // 1 (1 + 7) / 8 1 My edit to ClassIndex() in common.h should address this. I also had to change how class_to_size_ is initialized to prevent an 8 byte class size from being chosen later on. On 2011/08/20 02:40:30, jar wrote: > Note that they were distinguishing a class 0 for 0 length allocations, vs a > class 1 for 8 byte allocations. There are some subtlies in malloc about whether > we return a null pointer for a requested zero length allocation, vs a unique > pointer. I *think* tcmalloc goes with the standard of a unique pointer... so > I'm not sure why they distinguish this way... but you should be careful to watch > for checking where they might have optionally tried to support the other (NULL > return) standard, and can't (with the changes you made here). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/common.h:182: return (size_class < MIN_SIZE_CLASS) ? MIN_SIZE_CLASS : size_class; On 2011/08/20 02:40:30, jar wrote: > I assume this was added to preclude 8 byte allocations on a 64bit architecture. > > > As written, it adds a perf(?) hit near what looks to be highly optimized code. > My guess is that this was written expecting (hoping) to be inlined and they > wanted to stay really short and sweet. > > I like that you avoided broader changes (minimalist!), but perhaps it could be > written so that an optimizer could remove it when not active. Note that s and > the return value are both signed ints, so it is (I think) hard to tell when the > compiler needn't bother. > > Suggest you change line 182 to something like: > if (!AVOID_8_BYTE_CLASSES || size > 8) > return size_class; > return 2; // The smallest class that needs more than 8 bytes. > > That would allow the compiler to discard the comparison unless the macro was > set, and would have the fast-path(?) for the common case of returning size class > directly. > > I don't really know if this is perf critical... but it sure (to me) looks a bit > hand-tuned... and it is nice to have zero impact (guaranteed) when we are not > doing this twiddling. We know we have some perf impact when we are active (more > broadly)... and we can tune that case better if need be in the future. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:51: return *(reinterpret_cast<void**> (static_cast<void **>(t) + 1)); I am currently following the style in which the singly-linked list implementation accesses pointers. Would it be better to be consistent with their implementation or do it this way? On 2011/08/20 02:40:30, jar wrote: > I suspect (not sure) this code would be a lot cleaner if you defined a struct, > and routinely cast to pointer to that struct for manipulation. > > struct Node { > Node* next; > Node* prev; > }; > > You might even have helper functions: > void* VoidPointer(Node*); > Node* NodePointer(void*); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:65: ASSERT(FL_Next_No_Check(previous) == t); On 2011/08/20 02:40:30, jar wrote: > I would expect these to be places where we validate memory, and crash otherwise. > Why are you just doing a debug check? > > I think you should have two kinds of getters. One that does the check, and one > that doesn't. With the current code, many checks are repeated 3-5 times in > debug, and sometimes, you miss a check in release mode. Since you are really > hardening this, I'd suggest that the first pass create code that does all the > critical checking exactly once (per push or pop operation). If you decide you > want more (in Debug?), then add that on top. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:72: ASSERT(FL_Previous_No_Check(next) == t); On 2011/08/20 02:40:30, jar wrote: > Again, this this should IMO definitely be MEMORY_CHECK(), and not merely a debug > assertion. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:77: *(reinterpret_cast<void**> (static_cast<void **>(t) + 1)) = n; On 2011/08/20 02:40:30, jar wrote: > I don't think the second cast (on the left) is needed. > > You should probably standardize on reinterpret_cast<>, and also it would be much > better to have a struct, and not have to do explicit pointer arithmetic (re: ".. > + 1"). Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:93: // will point to the new head of the linked list. On 2011/08/20 02:40:30, jar wrote: > nit: use 80 characters of width so you don't need so many lines. Please do this > throughout the file. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:96: if (old == NULL) { // build singleton list I have been fixing this in my code, but I see that many of the existing shorter comments don't have a period at the end. On 2011/08/20 02:40:30, jar wrote: > nit: Comments should start with caps, be a complete sentence, and end with a > period. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:99: if (FL_Next(old)) On 2011/08/20 02:40:30, jar wrote: > This is going deeper into the list than any pointers we really need to depend on > or touch, so I don't know that you want to go there. You end up wondering where > you should stop. IMO, you should keep it to a minimum. This means you should > note every redundant value (back pointer) you set as the list takes possession > of the data, and be sure you check it (once) as it releases the data. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:100: MEMORY_CHECK(FL_Previous(FL_Next(old)), old); The potential issue I see with these NULL checks and all of the ones you mention below is that nothing in the original implementation requires any of these checks to pass. I agree that these checks are a good idea, however it forces us to make stronger assumptions. I'll add these in as an ASSERT for the time being. On 2011/08/20 02:40:30, jar wrote: > At best, you should use the *_No_Check versions in all MEMORY_CHECK() calls, as > the above repeats the same test effectively three times (currently in debug > mode). Additionally, line 99 does this test also in debug mode (making a total > of 4 runs). > > I think the test that was needed here and is missing is: > MEMORY_CHECK(FL_Prev_No_Check(old), NULL); > That ensures that the element that leads the list has not been placed into > another list since being pushed. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:113: void *result = *list; using ASSERT On 2011/08/20 02:40:30, jar wrote: > Here again I'd suggest the test: > > MEMORY_CHECK(FL_Prev_No_Check(result), NULL); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:114: if (result && FL_Next(result)) // pointer sanity check On 2011/08/20 02:40:30, jar wrote: > result is always non-null (unless we make a mistake in a pop). > > In fact, if result is null, then line 117 would segv. > > Line 117 would then be clearer on this point if it read: > *list = FL_Next(result); Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:115: MEMORY_CHECK(FL_Previous(FL_Next(result)), result); On 2011/08/20 02:40:30, jar wrote: > Again, the above does this same test for 3 times (plus one in line 114) in > debug. > > I think you should instead rely on line 117, which currently does this test a > 5th time, and make sure it does the test in non-debug mode. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:139: tmp = FL_Next(tmp); On 2011/08/20 02:40:30, jar wrote: > This code is definitely a place to do validation, and that is why I thought that > Fl_Next() should be doing it in non-debug mode. The cost is nothing, since > we're reading the other field of each block (cache lines should load both > addresses all the time). Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:146: MEMORY_CHECK(FL_Previous(FL_Next(*head)), *head); On 2011/08/20 02:40:30, jar wrote: > This is again going one step too far in the checking, as we have no dependency > on the next of the head. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:147: FL_SetPrevious(*head, NULL); On 2011/08/20 02:40:30, jar wrote: > This is seemingly a bug. We don't need to condition it on head having a next > value (as tested in line 145). We need to always set prev to NULL at the start > of the list. > > I'd suggest deleting line 146, and removing the condition FL_Next(*head) from > line 145. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:157: if (!start) return; We cannot make the assumption that if start is NULL then end will be null because what ends up happening is that tcmalloc will poprange, pop *start, and then pushrange. See ThreadCache::FetchFromCentralCache -> calls RemoveRange then PushRange(count, Next(start),end) {in both the original and my version, of course this could be changed} On 2011/08/20 02:40:30, jar wrote: > I'd suggest either asserting that end is NULL, or else not bothering to set it > on line 132. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:161: MEMORY_CHECK(FL_Previous(FL_Next(start)), start); Used ASSERT. On 2011/08/20 02:40:30, jar wrote: > I have mixed feelings about whether that test is critical... but I'm ok with it. > What you left out that is IMO significant is that > MEMORY_CHECK(FL_Previous_No_Check(start), NULL); > > Perhaps you don't care about that pointer (at the start of the list, but IMO, it > is good to keep this whole structure clean. If you want to leave it dangling, > you really need to say so up front (define the expected conditions at the ends > of the list). Line 65 suggested to me that the data is always either valid, or > NULL. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:163: MEMORY_CHECK(FL_Next(FL_Previous(end)), end); On 2011/08/20 02:40:30, jar wrote: > I'd also vote for a check here: > ASSERT(FL_Next_No_Check(end) == NULL); > > You set it on line 143, but I had a hard time spotting it, and assertion would > make it easier (for me) to see correctness. > > I'm fine for using assertions while we pass data between your methods, and using > the MEMORY_CHECK() when we get data back after having it out in circulation > (potentially getting overwritten) for any period of time. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:170: FL_SetPrevious(*head, end); Used ASSERT On 2011/08/20 02:40:30, jar wrote: > Again I'd like to first see a: > MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.h:40: // this generally means that each node needs at least 16 byes. The next What would be the proper way to check the type of architecture? (#ifdef ARCH_CPU_64_BITS ?) On 2011/08/20 02:40:30, jar wrote: > On a 32 bit platform, you don't need anything more than 8 bytes to hold two > pointers. > On a 64 bit machine, this will require 16 bytes (as you noted). > > It would probably be nice if you used that fact to reduce the amount of change > (i.e., continued to support classes with an 8 byte size on 32 bit > architectures). http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.h:59: #define MIN_SIZE_CLASS 2 On 2011/08/20 02:40:30, jar wrote: > This should really depend on 64 vs 32 bit architectures. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.h:108: *end = NULL; I included this check because I wanted to be consistent with the original code and provide the same guarantees. The original implementation of FL_PopRange is in free_list.h contains this code block. On 2011/08/20 02:40:30, jar wrote: > It is not a big deal... but this assignment to *end seems useless. I only > noticed it reading the changed code. When start is null, the end value is never > consulted (see line 124). > > In addition, I *think* we never pop a range of 0 items, so this whole block may > be wasteful (and at best should be coded as the uncommon path). It could have a > debug assertion... and I'm trying to check on use cases in chrome, but perhaps > in google3 it is used in more scenarios. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/tcmalloc.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/tcmalloc.cc:91: On 2011/08/20 02:40:30, jar wrote: > nit: don't add extra line. Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/thread_cache.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.cc:156: // Pop the top of the list and add the rest to the freelist On 2011/08/20 02:40:30, jar wrote: > nit: This file they do use periods at the end of the sentences, you should too. > I'd also expand on the comment: > > Pop the top of the list to return, and add the rest to the freelist. Done. Although they do not consistently use periods at the end of the sentences. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.cc:157: void *next = start; On 2011/08/20 02:40:30, jar wrote: > Perhaps a better name than |next| would be |second|. > The code is perfect, but I had to read it a few times to be sure I understood > it... and I'm *guessing* the name didn't help. (or it could be I was tired... or > worse). Done. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/thread_cache.h (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.h:45: #include "common.h" // for SizeMap, kMaxSize, etc I was removing duplicates of includes: common.h, page_heap_allocator.h, static_vars.h, sampler.h. I imagine we would want the duplicates to be removed. On 2011/08/20 02:40:30, jar wrote: > minimalist: don't reorder includes. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.h:47: #include "internal_logging.h" // for ASSERT, etc Ditto with the duplicated includes. On 2011/08/20 02:40:30, jar wrote: > again... don't reorder. http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/thread_cache.h:206: On 2011/08/20 02:40:30, jar wrote: > delete extra line. Done.
I just added a few nits from a quick skim. Given that Jim is way more familiar with the code, please defer to any of his suggestions over mine. http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/central_freelist.cc (right): http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/central_freelist.cc:95: void *next = span->objects; It looks like you left some debugging code behind. Shouldn't this line be removed, with "void* p = span->objects" in the loop initialization? http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/central_freelist.cc:316: FL_Push(&list, reinterpret_cast<void*>(ptr)); Shouldn't need the reinterpret cast here. http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:58: #if defined _LP64 For windows I'm pretty sure you'll need something like this: #if defined(_LP64) || defined(_WIN64) http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:60: #define AVOID_8_BYTE_CLASSES 1 I really dislike this macro name. Maybe something like IS_64_BIT_POINTERS. Or, is this macro just redundant with the class size macro? http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:61: #define FIRST_USABLE_SIZE_CLASS 2 I don't like this one either. Maybe something like MINIMUM_CLASS_SIZE would be better?
http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/central_freelist.cc (right): http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/central_freelist.cc:95: void *next = span->objects; Good catch. I don't even remember needing to debug this part. On 2011/08/24 17:22:30, Justin Schuh wrote: > It looks like you left some debugging code behind. Shouldn't this line be > removed, with "void* p = span->objects" in the loop initialization? http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/central_freelist.cc:316: FL_Push(&list, reinterpret_cast<void*>(ptr)); On 2011/08/24 17:22:30, Justin Schuh wrote: > Shouldn't need the reinterpret cast here. Done. I assumed I needed it because ptr is of type char*. http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:58: #if defined _LP64 On 2011/08/24 17:22:30, Justin Schuh wrote: > For windows I'm pretty sure you'll need something like this: > #if defined(_LP64) || defined(_WIN64) Done. As a general question: if the binaries we compile for 64bit windows are actually 32 bit applications, are the void * pointers 8 bytes? http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:60: #define AVOID_8_BYTE_CLASSES 1 On 2011/08/24 17:22:30, Justin Schuh wrote: > I really dislike this macro name. Maybe something like IS_64_BIT_POINTERS. Or, > is this macro just redundant with the class size macro? Done. http://codereview.chromium.org/7671034/diff/23003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:61: #define FIRST_USABLE_SIZE_CLASS 2 I need to allow for a size class for size 0 mallocs in all versions of the code, MIMIMUM_CLASS_SIZE doesn't seem to be what we really mean. On 2011/08/24 17:22:30, Justin Schuh wrote: > I don't like this one either. Maybe something like MINIMUM_CLASS_SIZE would be > better?
http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/6003/third_party/tcmalloc/chromiu... third_party/tcmalloc/chromium/src/free_list.cc:51: return *(reinterpret_cast<void**> (static_cast<void **>(t) + 1)); This file is entirely written by you, so things like spacing and comments and such should IMO be "current code style" compliant. Across files, I've never seen much style tainting, beyond header vs cc file, which use the same names for arguments, even in older styles IMO. A a general rule, I hate casts, as they tend to hide errors (being a C coder of the distant past... I've been burned too many times to count). As a result, I vastly prefer (if not forced by style compatibility) to minimize the number of places I have to cast. For instance, having a lone pair of helper functions that do the pair of casts you need, would be nicer. It would also have caught (via type checking!) the duplicate cast I noticed. If you want to hold with the other files style, that is ok, but when allowed, I'd opt for newer and better style. On 2011/08/24 00:19:24, bxx wrote: > I am currently following the style in which the singly-linked list > implementation accesses pointers. Would it be better to be consistent with > their implementation or do it this way? > On 2011/08/20 02:40:30, jar wrote: > > I suspect (not sure) this code would be a lot cleaner if you defined a struct, > > and routinely cast to pointer to that struct for manipulation. > > > > struct Node { > > Node* next; > > Node* prev; > > }; > > > > You might even have helper functions: > > void* VoidPointer(Node*); > > Node* NodePointer(void*); > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/central_freelist.cc (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/central_freelist.cc:321: span->objects = list; nit: You may as well move this to between line 319 and 320, so that the diff will be minimized (that is where you cut a line in the original). http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/common.cc (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/common.cc:160: class_to_size_[FIRST_USABLE_SIZE_CLASS]; This was cute :-). I expect some tests or assertion will detect this anomaly... but that seems fine. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:50: return *(reinterpret_cast<void**> (reinterpret_cast<void **>(t) + 1)); The second cast, on the left, appears redundant, and should be removed. You already had the desired type... and had just incremented the pointer... but still had the same type as a result. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:105: // upates *list to point to the next element in the list. Return the typo: upates-->updates http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:111: *list = FL_Next(result); // Fixes remainder of list. Not sure what comment means... probably you should delete it. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:145: // located at start and ends at he node end into the linked list at typo: "at he node" --> "at the node" IMO, you should put vertical bars around variable names in comments. It will make all the comments in this file much more readable. You'll probably get away with fewer words as well. For instance, the above comment would become: "Pushes the nodes of the doubly linked list beginning at |start| and ending at |end| into the linked list at |*head|. |*head| is updated to point to the new head of the list. |head| must not be null." Note that as I rewrote it, I also realized the last sentence was mistaken, as |head| must not be null, but |*head| can be null, and this fact is handled on line 158. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:159: ASSERT(FL_Previous_No_Check(*head) == NULL); This is a critical check, and should not be debug only. Suggest: MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:160: FL_Next(*head); IMO, you shouldn't bother with this interior check of the list, other than in debug mode (at most). Once you start to drift into the list, the question is how far should you go? This test is also far from free, as it refers to memory that would not have to be touched during this call. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:32: // functions that implement singly linked lists. The basic singly wording nit: I think you meant to say "declarations" of doubly linked list functions, and "definitions" of singly linked list functionality. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:33: // linked list functions use void * as storage. The original author wording nit: "The basic singly linked list functions use void * as storage." The phrase "as storage" doesn't seem meaningful, and there is no mention that these lists are null terminated. better might be something like: "The singly linked lists are null terminated, and use raw to pointers to link to successive elements, and the pointers are held at the start of each element, independent of the element's size." http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:34: // of that code is Sanjay Ghemawat <opensource@google.com> The basic nit: Period before "The basic" http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:36: // * pointers directly inline. A node of this list needs to be big wording nit: the phrase "directly inline" is also unclear to me. Better might be something like: "The doubly linked lists are null terminated at both ends, and use raw pointers to point to adjacent elements." To be honest, I don't think this prose needs any mention of "void* pointers" and should just say "pointers." I think the mention of void* is an implementation detail that probably will only add confusion to the prose. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:37: // enough to hold 2 void * pointers, this generally means that each nit: We always put the * next to the type, with no intervening spaces. You also use passive voice when discussing what a "list needs." Suggest wording like: "As a result, elements in doubly linked lists are required to be large enough to hold two raw pointers if doubly linked lists are employed, and to hold one pointer if singly linked lists are employed. On machines with 64bit pointers, this means elements must be at least 16 bytes in size for doubly linked list support, and 8 bytes for singly linked list support." http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:39: // is written into the first 8 bytes of the node and the previous nit: this sentence has facts only applicable to 64 bit machines... but there is no qualifier (i.e., next pointer is written to first 4 bytes on a 32 bit machine discussed). Please clean this up in some way. You might put the doubly-linked list description atop the section for them. Please try to use prose, but be terse and to the point. For instance, the comment on line 42 about "fairly arbitrary, but consistent" doesn't seem to carry much information. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:64: #define FIRST_USABLE_SIZE_CLASS 1 This name is still a bit odd, as there is a size class of 0 that is usable (or is it??). Perhaps something like: ALLOW_8_BYTE_SIZE_CLASS. or: ALLOW_8_BYTE_SIZE_CLASS_1
Class size code seems a little hacky at the moment. I considered cleaning it up by putting everything of size 1-16 in a single class, but that would require more involved code edits. If we decide this is something we want, I would like to save the work for a future code review. Hopefully my macro names are clearer. I didn't want to change the semantics of the macros because I liked having a macro defining the class size information instead of just a boolean to allow for more readable code. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/central_freelist.cc (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/central_freelist.cc:321: span->objects = list; On 2011/08/25 02:07:50, jar wrote: > nit: You may as well move this to between line 319 and 320, so that the diff > will be minimized (that is where you cut a line in the original). Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/common.cc (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/common.cc:160: class_to_size_[FIRST_USABLE_SIZE_CLASS]; On 2011/08/25 02:07:50, jar wrote: > This was cute :-). I expect some tests or assertion will detect this anomaly... > but that seems fine. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:50: return *(reinterpret_cast<void**> (reinterpret_cast<void **>(t) + 1)); On 2011/08/25 02:07:50, jar wrote: > The second cast, on the left, appears redundant, and should be removed. You > already had the desired type... and had just incremented the pointer... but > still had the same type as a result. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:105: // upates *list to point to the next element in the list. Return the On 2011/08/25 02:07:50, jar wrote: > typo: upates-->updates Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:111: *list = FL_Next(result); // Fixes remainder of list. On 2011/08/25 02:07:50, jar wrote: > Not sure what comment means... probably you should delete it. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:145: // located at start and ends at he node end into the linked list at On 2011/08/25 02:07:50, jar wrote: > typo: "at he node" --> "at the node" > > IMO, you should put vertical bars around variable names in comments. It will > make all the comments in this file much more readable. You'll probably get away > with fewer words as well. For instance, the above comment would become: > > "Pushes the nodes of the doubly linked list beginning at |start| and ending at > |end| into the linked list at |*head|. |*head| is updated to point to the new > head of the list. |head| must not be null." > > Note that as I rewrote it, I also realized the last sentence was mistaken, as > |head| must not be null, but |*head| can be null, and this fact is handled on > line 158. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:159: ASSERT(FL_Previous_No_Check(*head) == NULL); On 2011/08/25 02:07:50, jar wrote: > This is a critical check, and should not be debug only. Suggest: > MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:160: FL_Next(*head); On 2011/08/25 02:07:50, jar wrote: > IMO, you shouldn't bother with this interior check of the list, other than in > debug mode (at most). Once you start to drift into the list, the question is > how far should you go? This test is also far from free, as it refers to memory > that would not have to be touched during this call. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:32: // functions that implement singly linked lists. The basic singly On 2011/08/25 02:07:50, jar wrote: > wording nit: I think you meant to say "declarations" of doubly linked list > functions, and "definitions" of singly linked list functionality. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:33: // linked list functions use void * as storage. The original author On 2011/08/25 02:07:50, jar wrote: > wording nit: "The basic singly linked list functions use void * as storage." > > The phrase "as storage" doesn't seem meaningful, and there is no mention that > these lists are null terminated. > > better might be something like: > > "The singly linked lists are null terminated, and use raw to pointers to link to > successive elements, and the pointers are held at the start of each element, > independent of the element's size." Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:34: // of that code is Sanjay Ghemawat <opensource@google.com> The basic On 2011/08/25 02:07:50, jar wrote: > nit: Period before "The basic" Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:36: // * pointers directly inline. A node of this list needs to be big On 2011/08/25 02:07:50, jar wrote: > wording nit: the phrase "directly inline" is also unclear to me. > > Better might be something like: > > "The doubly linked lists are null terminated at both ends, and use raw pointers > to point to adjacent elements." > > To be honest, I don't think this prose needs any mention of "void* pointers" and > should just say "pointers." I think the mention of void* is an implementation > detail that probably will only add confusion to the prose. Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:37: // enough to hold 2 void * pointers, this generally means that each On 2011/08/25 02:07:50, jar wrote: > nit: We always put the * next to the type, with no intervening spaces. > > You also use passive voice when discussing what a "list needs." > > Suggest wording like: > > "As a result, elements in doubly linked lists are required to be large enough to > hold two raw pointers if doubly linked lists are employed, and to hold one > pointer if singly linked lists are employed. On machines with 64bit pointers, > this means elements must be at least 16 bytes in size for doubly linked list > support, and 8 bytes for singly linked list support." Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:39: // is written into the first 8 bytes of the node and the previous On 2011/08/25 02:07:50, jar wrote: > nit: this sentence has facts only applicable to 64 bit machines... but there is > no qualifier (i.e., next pointer is written to first 4 bytes on a 32 bit machine > discussed). > > Please clean this up in some way. You might put the doubly-linked list > description atop the section for them. > > Please try to use prose, but be terse and to the point. For instance, the > comment on line 42 about "fairly arbitrary, but consistent" doesn't seem to > carry much information. > Done. http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:64: #define FIRST_USABLE_SIZE_CLASS 1 On 2011/08/25 02:07:50, jar wrote: > This name is still a bit odd, as there is a size class of 0 that is usable (or > is it??). > Perhaps something like: > ALLOW_8_BYTE_SIZE_CLASS. > or: > ALLOW_8_BYTE_SIZE_CLASS_1 Done.
This is looking much nicer. A few more comments below... and perhaps you'll get a chance to test land tonight ;-). Thanks! http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/common.h (right): http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/common.h:181: return FIRST_NON_0_SIZE_CLASS; I haven't measured it... but I've been told that compilers optimize for the if-true case, and assume that is most likely. The if-false case generally requires a branch (and is slower). As a result, I liked the code you had in the last version better (since this seems to be a heavilly optimized piece of code). Possibly even better would be to test last for for the (rarer) s == 0 case. The code would then read: if (!HAS_64_BIT_POINTERS || (size_class > FIRST_NON_0_SIZE_CLASS) || (s == 0)) return size_class; return FIRST_NON_0_SIZE_CLASS; http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:51: return *(reinterpret_cast<void **>(t) + 1); style nit: don't leave spaces after type, and before star. optional nit: Since you don't like using a struct... how about: return (reinterpret_cast<void**>(t)[1]; The existing expression is kindred to saying: *(array + 1) when all you wanted was: array[1] You can make similar expressions for the previous pointer and the next pointer (using [0] to get and set next pointers). http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:84: // Makes the memory pointed at |t| a singleton doubly linked list. nit: "...memory pointed at |t| ..." should be: " ...memory pointed to by |t| ..." alternatively, you could say: " ... element at |t| ..." http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:109: // linked list. |*list| must not be NULL. The last line should read: "|list| must not be NULL." See line 114 where you specifically deal with *list being null. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:124: // |*head| must not be NULL. nit: Delete line 124. *head can be null IFF N == 0. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:125: void FL_PopRange(void **head, int N, void **start, void **end) { nit: N ---> n http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:90: void FL_PopRange(void **head, int N, void **start, void **end); nit: even if the old code (below) used an upper case N, you should probably use a lower case N in this new code.
Hopefully these will be the last set of changes. I kicked off the trybots, but given the nature of the changes, I should have already run into problems if new bugs were introduced. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/common.h (right): http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/common.h:181: return FIRST_NON_0_SIZE_CLASS; On 2011/08/26 18:56:29, jar wrote: > I haven't measured it... but I've been told that compilers optimize for the > if-true case, and assume that is most likely. The if-false case generally > requires a branch (and is slower). As a result, I liked the code you had in the > last version better (since this seems to be a heavilly optimized piece of code). > Possibly even better would be to test last for for the (rarer) s == 0 case. > The code would then read: > > if (!HAS_64_BIT_POINTERS || > (size_class > FIRST_NON_0_SIZE_CLASS) || (s == 0)) > return size_class; > return FIRST_NON_0_SIZE_CLASS; > Done. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:51: return *(reinterpret_cast<void **>(t) + 1); On 2011/08/26 18:56:29, jar wrote: > style nit: don't leave spaces after type, and before star. > > optional nit: Since you don't like using a struct... how about: > > return (reinterpret_cast<void**>(t)[1]; > > The existing expression is kindred to saying: > *(array + 1) > when all you wanted was: > array[1] > > You can make similar expressions for the previous pointer and the next pointer > (using [0] to get and set next pointers). Done. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:84: // Makes the memory pointed at |t| a singleton doubly linked list. On 2011/08/26 18:56:29, jar wrote: > nit: "...memory pointed at |t| ..." > should be: > > " ...memory pointed to by |t| ..." > > alternatively, you could say: > > " ... element at |t| ..." Done. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:109: // linked list. |*list| must not be NULL. On 2011/08/26 18:56:29, jar wrote: > The last line should read: > > "|list| must not be NULL." > > See line 114 where you specifically deal with *list being null. Done. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:124: // |*head| must not be NULL. On 2011/08/26 18:56:29, jar wrote: > nit: Delete line 124. *head can be null IFF N == 0. Done. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:125: void FL_PopRange(void **head, int N, void **start, void **end) { On 2011/08/26 18:56:29, jar wrote: > nit: N ---> n Original implementation uses N. http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/32004/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:90: void FL_PopRange(void **head, int N, void **start, void **end); On 2011/08/26 18:56:29, jar wrote: > nit: even if the old code (below) used an upper case N, you should probably use > a lower case N in this new code. Done.
As I mentioned, I'd really like to see this land separately from other checkins, so that we can see any/all impact on the perfbots. To do this, it is best to land late at night (or on a weekend), when the tree is idle. To guarantee a solo landing, you can change the status of the tree to "tree closed: bxx landing needs to get solo perf results. Will repoen in just 2 minutes" Be sure the tree has no builds in progress... land... watch till all the builds kick off... and then re-open the tree. LGTM Thanks!
Two things I failed to point out: a) All the SLL_* code should be referenced, rather than repeated. IT is makes it clearer that this is a no-op, and reuses existing code (which might be improved over time). b) It woul be great to get a review by Sanjay, to see if he felt good about the code, or had suggestions. Although it would be nice to land ASAP, it would be good to get Sanjay's blessings (and changes), so that you'd have at least a chance of upstreaming it (or understand why it was not appropriate). Sorry for focusing so much on the review of changed code, and forgetting about the second point, and missing the first. Jim http://codereview.chromium.org/7671034/diff/39003/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/39003/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:100: return *(reinterpret_cast<void**>(t)); I appologize for not thinking of this sooner: It would be better to reference the existing SLL_*() code here, than to re-write it. Hence this function woul dsimply refere to: returrn SLL_NEXT(v); Same for all functions for which there was a well-defined SLL_* varient.
Sorry, I had some git issues and also screwed up the last patch on this code review so your last set of comments got lost. I made the changes requested by your previous comment. On 2011/08/29 09:59:39, jar wrote: > Two things I failed to point out: > > a) All the SLL_* code should be referenced, rather than repeated. IT is makes > it clearer that this is a no-op, and reuses existing code (which might be > improved over time). > > b) It woul be great to get a review by Sanjay, to see if he felt good about the > code, or had suggestions. > > Although it would be nice to land ASAP, it would be good to get Sanjay's > blessings (and changes), so that you'd have at least a chance of upstreaming it > (or understand why it was not appropriate). > > Sorry for focusing so much on the review of changed code, and forgetting about > the second point, and missing the first. > > Jim > > http://codereview.chromium.org/7671034/diff/39003/third_party/tcmalloc/chromi... > File third_party/tcmalloc/chromium/src/free_list.h (right): > > http://codereview.chromium.org/7671034/diff/39003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:100: return > *(reinterpret_cast<void**>(t)); > I appologize for not thinking of this sooner: > > It would be better to reference the existing SLL_*() code here, than to re-write > it. Hence this function woul dsimply refere to: > returrn SLL_NEXT(v); > > Same for all functions for which there was a well-defined SLL_* varient.
http://codereview.chromium.org/7671034/diff/44013/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/44013/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:135: inline size_t FL_Size(void *head) { You should probably push this inside the ifdef, and provide your own implementation that checks the back-pointers as it traverses the list. As it stands, this has dependencies on the implementation of your doubly-linked lists that are best left abstract in your private implementation (in case you change and harden this implementation further).
http://codereview.chromium.org/7671034/diff/44013/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.h (right): http://codereview.chromium.org/7671034/diff/44013/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.h:135: inline size_t FL_Size(void *head) { On 2011/08/29 19:37:46, jar wrote: > You should probably push this inside the ifdef, and provide your own > implementation that checks the back-pointers as it traverses the list. > > As it stands, this has dependencies on the implementation of your doubly-linked > lists that are best left abstract in your private implementation (in case you > change and harden this implementation further). Done.
http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:168: int count = 0; Please validate: MEMORY_CHECK(FL_Previous_No_Check(*head), NULL);
http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:168: int count = 0; On 2011/08/29 20:55:21, jar wrote: > Please validate: > MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); Used assert because original implementation doesn't require Size() to be called on head of list.
http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:168: int count = 0; The original implementation (via SLL_*) appears to be more generic, and hence may need to service other users in such strange contexts. Your implementation is specifically only for the allocator (at least currently). If you agree enough that you would put in an assert, then you have established the "contract" and no caller should ever pass in anything but the head of a list... which means the MEMORY_CHECK is appropriate (and actually cost free... since the reading of the "next" pointer will load the cache line, facilitating reading of the "prev" pointer, and vice versa). I thought the only use was when called with the head of the list. Looking closer, I don't see any uses of it at all in the codebase. IMO, you should use MEMORY_CHECK() to validate the list maximally at runtime (in conformance to your ASSERT stated contract). On 2011/08/29 21:38:13, bxx wrote: > On 2011/08/29 20:55:21, jar wrote: > > Please validate: > > MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); > > Used assert because original implementation doesn't require Size() to be called > on head of list.
http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... File third_party/tcmalloc/chromium/src/free_list.cc (right): http://codereview.chromium.org/7671034/diff/50001/third_party/tcmalloc/chromi... third_party/tcmalloc/chromium/src/free_list.cc:168: int count = 0; On 2011/08/29 21:54:33, jar wrote: > The original implementation (via SLL_*) appears to be more generic, and hence > may need to service other users in such strange contexts. Your implementation > is specifically only for the allocator (at least currently). > > If you agree enough that you would put in an assert, then you have established > the "contract" and no caller should ever pass in anything but the head of a > list... which means the MEMORY_CHECK is appropriate (and actually cost free... > since the reading of the "next" pointer will load the cache line, facilitating > reading of the "prev" pointer, and vice versa). > > I thought the only use was when called with the head of the list. Looking > closer, I don't see any uses of it at all in the codebase. > > IMO, you should use MEMORY_CHECK() to validate the list maximally at runtime (in > conformance to your ASSERT stated contract). > > On 2011/08/29 21:38:13, bxx wrote: > > On 2011/08/29 20:55:21, jar wrote: > > > Please validate: > > > MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); > > > > Used assert because original implementation doesn't require Size() to be > called > > on head of list. > Fair enough.
LGTM... and you should ask Sanjay if he'd like to review and comment. Thanks!
base LGTM rubberstamp
http://build.chromium.org/p/chromium/builders/Linux%20Tests%20%28Views%20dbg%... NetworkScreenTest.Cellular seems to fail flakily in shutdown with messages like: === [ OK ] NetworkScreenTest.Cellular (307 ms) [----------] 1 test from NetworkScreenTest (307 ms total) [----------] Global test environment tear-down [==========] 1 test from 1 test case ran. (307 ms total) [ PASSED ] 1 test. third_party/tcmalloc/chromium/src/free_list.cc:105] Memory corruption detected. YOU HAVE 34 FLAKY TESTS YOU HAVE 4 tests with ignored failures (FAILS prefix) [12862:12862:0912/223005:802569153:ERROR:process_util_posix.cc(134)] Received signal 6 third_party/tcmalloc/chromium/src/free_list.cc:105] Memory corruption detected. [12862:12862:0912/223006:803044826:ERROR:process_util_posix.cc(134)] Received signal 6 third_party/tcmalloc/chromium/src/free_list.cc:105] Memory corruption detected. === Is something up? Is there memory corruption here? On Thu, Aug 25, 2011 at 1:23 PM, <bxx@chromium.org> wrote: > Class size code seems a little hacky at the moment. I considered cleaning > it up > by putting everything of size 1-16 in a single class, but that would require > more involved code edits. If we decide this is something we want, I would > like > to save the work for a future code review. > > Hopefully my macro names are clearer. I didn't want to change the semantics > of > the macros because I liked having a macro defining the class size > information > instead of just a boolean to allow for more readable code. > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > File third_party/tcmalloc/chromium/src/central_freelist.cc (right): > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/central_freelist.cc:321: span->objects > = list; > On 2011/08/25 02:07:50, jar wrote: >> >> nit: You may as well move this to between line 319 and 320, so that > > the diff >> >> will be minimized (that is where you cut a line in the original). > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > File third_party/tcmalloc/chromium/src/common.cc (right): > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/common.cc:160: > class_to_size_[FIRST_USABLE_SIZE_CLASS]; > On 2011/08/25 02:07:50, jar wrote: >> >> This was cute :-). I expect some tests or assertion will detect this > > anomaly... >> >> but that seems fine. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > File third_party/tcmalloc/chromium/src/free_list.cc (right): > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.cc:50: return > *(reinterpret_cast<void**> (reinterpret_cast<void **>(t) + 1)); > On 2011/08/25 02:07:50, jar wrote: >> >> The second cast, on the left, appears redundant, and should be > > removed. You >> >> already had the desired type... and had just incremented the > > pointer... but >> >> still had the same type as a result. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.cc:105: // upates *list to > point to the next element in the list. Return the > On 2011/08/25 02:07:50, jar wrote: >> >> typo: upates-->updates > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.cc:111: *list = > FL_Next(result); // Fixes remainder of list. > On 2011/08/25 02:07:50, jar wrote: >> >> Not sure what comment means... probably you should delete it. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.cc:145: // located at start > and ends at he node end into the linked list at > On 2011/08/25 02:07:50, jar wrote: >> >> typo: "at he node" --> "at the node" > >> IMO, you should put vertical bars around variable names in comments. > > It will >> >> make all the comments in this file much more readable. You'll > > probably get away >> >> with fewer words as well. For instance, the above comment would > > become: > >> "Pushes the nodes of the doubly linked list beginning at |start| and > > ending at >> >> |end| into the linked list at |*head|. |*head| is updated to point to > > the new >> >> head of the list. |head| must not be null." > >> Note that as I rewrote it, I also realized the last sentence was > > mistaken, as >> >> |head| must not be null, but |*head| can be null, and this fact is > > handled on >> >> line 158. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.cc:159: > ASSERT(FL_Previous_No_Check(*head) == NULL); > On 2011/08/25 02:07:50, jar wrote: >> >> This is a critical check, and should not be debug only. Suggest: >> MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.cc:160: FL_Next(*head); > On 2011/08/25 02:07:50, jar wrote: >> >> IMO, you shouldn't bother with this interior check of the list, other > > than in >> >> debug mode (at most). Once you start to drift into the list, the > > question is >> >> how far should you go? This test is also far from free, as it refers > > to memory >> >> that would not have to be touched during this call. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > File third_party/tcmalloc/chromium/src/free_list.h (right): > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:32: // functions that > implement singly linked lists. The basic singly > On 2011/08/25 02:07:50, jar wrote: >> >> wording nit: I think you meant to say "declarations" of doubly linked > > list >> >> functions, and "definitions" of singly linked list functionality. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:33: // linked list > functions use void * as storage. The original author > On 2011/08/25 02:07:50, jar wrote: >> >> wording nit: "The basic singly linked list functions use void * as > > storage." > >> The phrase "as storage" doesn't seem meaningful, and there is no > > mention that >> >> these lists are null terminated. > >> better might be something like: > >> "The singly linked lists are null terminated, and use raw to pointers > > to link to >> >> successive elements, and the pointers are held at the start of each > > element, >> >> independent of the element's size." > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:34: // of that code is > Sanjay Ghemawat <opensource@google.com> The basic > On 2011/08/25 02:07:50, jar wrote: >> >> nit: Period before "The basic" > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:36: // * pointers directly > inline. A node of this list needs to be big > On 2011/08/25 02:07:50, jar wrote: >> >> wording nit: the phrase "directly inline" is also unclear to me. > >> Better might be something like: > >> "The doubly linked lists are null terminated at both ends, and use raw > > pointers >> >> to point to adjacent elements." > >> To be honest, I don't think this prose needs any mention of "void* > > pointers" and >> >> should just say "pointers." I think the mention of void* is an > > implementation >> >> detail that probably will only add confusion to the prose. > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:37: // enough to hold 2 > void * pointers, this generally means that each > On 2011/08/25 02:07:50, jar wrote: >> >> nit: We always put the * next to the type, with no intervening spaces. > > >> You also use passive voice when discussing what a "list needs." > >> Suggest wording like: > >> "As a result, elements in doubly linked lists are required to be large > > enough to >> >> hold two raw pointers if doubly linked lists are employed, and to hold > > one >> >> pointer if singly linked lists are employed. On machines with 64bit > > pointers, >> >> this means elements must be at least 16 bytes in size for doubly > > linked list >> >> support, and 8 bytes for singly linked list support." > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:39: // is written into the > first 8 bytes of the node and the previous > On 2011/08/25 02:07:50, jar wrote: >> >> nit: this sentence has facts only applicable to 64 bit machines... but > > there is >> >> no qualifier (i.e., next pointer is written to first 4 bytes on a 32 > > bit machine >> >> discussed). > >> Please clean this up in some way. You might put the doubly-linked > > list >> >> description atop the section for them. > >> Please try to use prose, but be terse and to the point. For instance, > > the >> >> comment on line 42 about "fairly arbitrary, but consistent" doesn't > > seem to >> >> carry much information. > > > Done. > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > third_party/tcmalloc/chromium/src/free_list.h:64: #define > FIRST_USABLE_SIZE_CLASS 1 > On 2011/08/25 02:07:50, jar wrote: >> >> This name is still a bit odd, as there is a size class of 0 that is > > usable (or >> >> is it??). >> Perhaps something like: >> ALLOW_8_BYTE_SIZE_CLASS. >> or: >> ALLOW_8_BYTE_SIZE_CLASS_1 > > Done. > > http://codereview.chromium.org/7671034/ >
On Mon, Sep 12, 2011 at 11:15 PM, William Chan (陈智昌) <willchan@chromium.org>wrote: > > http://build.chromium.org/p/chromium/builders/Linux%20Tests%20%28Views%20dbg%... > > NetworkScreenTest.Cellular seems to fail flakily in shutdown with messages > like: > > === > > [ OK ] NetworkScreenTest.Cellular (307 ms) > [----------] 1 test from NetworkScreenTest (307 ms total) > > [----------] Global test environment tear-down > [==========] 1 test from 1 test case ran. (307 ms total) > [ PASSED ] 1 test. > third_party/tcmalloc/chromium/src/free_list.cc:105] Memory corruption > detected. > YOU HAVE 34 FLAKY TESTS > > YOU HAVE 4 tests with ignored failures (FAILS prefix) > > [12862:12862:0912/223005:802569153:ERROR:process_util_posix.cc(134)] > Received signal 6 > third_party/tcmalloc/chromium/src/free_list.cc:105] Memory corruption > detected. > [12862:12862:0912/223006:803044826:ERROR:process_util_posix.cc(134)] > Received signal 6 > third_party/tcmalloc/chromium/src/free_list.cc:105] Memory corruption > detected. > > === > > Is something up? Is there memory corruption here? > That seems most likely. This change just checks that TCMalloc's free-list pointers are valid (and right now it's turned on for debug builds only). If chunks in the free-list have invalid pointers, it almost certainly means that something is stepping on free chunks, or using them after being freed. Do you know if anyone has checked this under TSAN? It provides a lot more useful information for tracking these down after they've been verified. -j > > On Thu, Aug 25, 2011 at 1:23 PM, <bxx@chromium.org> wrote: > > Class size code seems a little hacky at the moment. I considered > cleaning > > it up > > by putting everything of size 1-16 in a single class, but that would > require > > more involved code edits. If we decide this is something we want, I > would > > like > > to save the work for a future code review. > > > > Hopefully my macro names are clearer. I didn't want to change the > semantics > > of > > the macros because I liked having a macro defining the class size > > information > > instead of just a boolean to allow for more readable code. > > > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > File third_party/tcmalloc/chromium/src/central_freelist.cc (right): > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/central_freelist.cc:321: span->objects > > = list; > > On 2011/08/25 02:07:50, jar wrote: > >> > >> nit: You may as well move this to between line 319 and 320, so that > > > > the diff > >> > >> will be minimized (that is where you cut a line in the original). > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > File third_party/tcmalloc/chromium/src/common.cc (right): > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/common.cc:160: > > class_to_size_[FIRST_USABLE_SIZE_CLASS]; > > On 2011/08/25 02:07:50, jar wrote: > >> > >> This was cute :-). I expect some tests or assertion will detect this > > > > anomaly... > >> > >> but that seems fine. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > File third_party/tcmalloc/chromium/src/free_list.cc (right): > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.cc:50: return > > *(reinterpret_cast<void**> (reinterpret_cast<void **>(t) + 1)); > > On 2011/08/25 02:07:50, jar wrote: > >> > >> The second cast, on the left, appears redundant, and should be > > > > removed. You > >> > >> already had the desired type... and had just incremented the > > > > pointer... but > >> > >> still had the same type as a result. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.cc:105: // upates *list to > > point to the next element in the list. Return the > > On 2011/08/25 02:07:50, jar wrote: > >> > >> typo: upates-->updates > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.cc:111: *list = > > FL_Next(result); // Fixes remainder of list. > > On 2011/08/25 02:07:50, jar wrote: > >> > >> Not sure what comment means... probably you should delete it. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.cc:145: // located at start > > and ends at he node end into the linked list at > > On 2011/08/25 02:07:50, jar wrote: > >> > >> typo: "at he node" --> "at the node" > > > >> IMO, you should put vertical bars around variable names in comments. > > > > It will > >> > >> make all the comments in this file much more readable. You'll > > > > probably get away > >> > >> with fewer words as well. For instance, the above comment would > > > > become: > > > >> "Pushes the nodes of the doubly linked list beginning at |start| and > > > > ending at > >> > >> |end| into the linked list at |*head|. |*head| is updated to point to > > > > the new > >> > >> head of the list. |head| must not be null." > > > >> Note that as I rewrote it, I also realized the last sentence was > > > > mistaken, as > >> > >> |head| must not be null, but |*head| can be null, and this fact is > > > > handled on > >> > >> line 158. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.cc:159: > > ASSERT(FL_Previous_No_Check(*head) == NULL); > > On 2011/08/25 02:07:50, jar wrote: > >> > >> This is a critical check, and should not be debug only. Suggest: > >> MEMORY_CHECK(FL_Previous_No_Check(*head), NULL); > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.cc:160: FL_Next(*head); > > On 2011/08/25 02:07:50, jar wrote: > >> > >> IMO, you shouldn't bother with this interior check of the list, other > > > > than in > >> > >> debug mode (at most). Once you start to drift into the list, the > > > > question is > >> > >> how far should you go? This test is also far from free, as it refers > > > > to memory > >> > >> that would not have to be touched during this call. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > File third_party/tcmalloc/chromium/src/free_list.h (right): > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:32: // functions that > > implement singly linked lists. The basic singly > > On 2011/08/25 02:07:50, jar wrote: > >> > >> wording nit: I think you meant to say "declarations" of doubly linked > > > > list > >> > >> functions, and "definitions" of singly linked list functionality. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:33: // linked list > > functions use void * as storage. The original author > > On 2011/08/25 02:07:50, jar wrote: > >> > >> wording nit: "The basic singly linked list functions use void * as > > > > storage." > > > >> The phrase "as storage" doesn't seem meaningful, and there is no > > > > mention that > >> > >> these lists are null terminated. > > > >> better might be something like: > > > >> "The singly linked lists are null terminated, and use raw to pointers > > > > to link to > >> > >> successive elements, and the pointers are held at the start of each > > > > element, > >> > >> independent of the element's size." > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:34: // of that code is > > Sanjay Ghemawat <opensource@google.com> The basic > > On 2011/08/25 02:07:50, jar wrote: > >> > >> nit: Period before "The basic" > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:36: // * pointers directly > > inline. A node of this list needs to be big > > On 2011/08/25 02:07:50, jar wrote: > >> > >> wording nit: the phrase "directly inline" is also unclear to me. > > > >> Better might be something like: > > > >> "The doubly linked lists are null terminated at both ends, and use raw > > > > pointers > >> > >> to point to adjacent elements." > > > >> To be honest, I don't think this prose needs any mention of "void* > > > > pointers" and > >> > >> should just say "pointers." I think the mention of void* is an > > > > implementation > >> > >> detail that probably will only add confusion to the prose. > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:37: // enough to hold 2 > > void * pointers, this generally means that each > > On 2011/08/25 02:07:50, jar wrote: > >> > >> nit: We always put the * next to the type, with no intervening spaces. > > > > > >> You also use passive voice when discussing what a "list needs." > > > >> Suggest wording like: > > > >> "As a result, elements in doubly linked lists are required to be large > > > > enough to > >> > >> hold two raw pointers if doubly linked lists are employed, and to hold > > > > one > >> > >> pointer if singly linked lists are employed. On machines with 64bit > > > > pointers, > >> > >> this means elements must be at least 16 bytes in size for doubly > > > > linked list > >> > >> support, and 8 bytes for singly linked list support." > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:39: // is written into the > > first 8 bytes of the node and the previous > > On 2011/08/25 02:07:50, jar wrote: > >> > >> nit: this sentence has facts only applicable to 64 bit machines... but > > > > there is > >> > >> no qualifier (i.e., next pointer is written to first 4 bytes on a 32 > > > > bit machine > >> > >> discussed). > > > >> Please clean this up in some way. You might put the doubly-linked > > > > list > >> > >> description atop the section for them. > > > >> Please try to use prose, but be terse and to the point. For instance, > > > > the > >> > >> comment on line 42 about "fairly arbitrary, but consistent" doesn't > > > > seem to > >> > >> carry much information. > > > > > > Done. > > > > > http://codereview.chromium.org/7671034/diff/25003/third_party/tcmalloc/chromi... > > third_party/tcmalloc/chromium/src/free_list.h:64: #define > > FIRST_USABLE_SIZE_CLASS 1 > > On 2011/08/25 02:07:50, jar wrote: > >> > >> This name is still a bit odd, as there is a size class of 0 that is > > > > usable (or > >> > >> is it??). > >> Perhaps something like: > >> ALLOW_8_BYTE_SIZE_CLASS. > >> or: > >> ALLOW_8_BYTE_SIZE_CLASS_1 > > > > Done. > > > > http://codereview.chromium.org/7671034/ > > >
I would be interested in seeing how this looks under ASAN. I haven't been able to repro the failed checks yet -- I am having problems building the tree at the revision listed in the Builder Linux Tests report, so please let me know if you beat me to it. -Rebecca On Tue, Sep 13, 2011 at 8:19 AM, Justin Schuh <jschuh@chromium.org> wrote: > > > That seems most likely. This change just checks that TCMalloc's free-list > pointers are valid (and right now it's turned on for debug builds only). If > chunks in the free-list have invalid pointers, it almost certainly means > that something is stepping on free chunks, or using them after being freed. > > Do you know if anyone has checked this under TSAN? It provides a lot more > useful information for tracking these down after they've been verified. > > -j > >
D'oh, I meant ASAN, not TSAN. -j On Tue, Sep 13, 2011 at 11:15 AM, Rebecca Shapiro <bxx@google.com> wrote: > I would be interested in seeing how this looks under ASAN. I haven't been > able to repro the failed checks yet -- I am having problems building the > tree at the revision listed in the Builder Linux Tests report, so please let > me know if you beat me to it. > > -Rebecca > > > On Tue, Sep 13, 2011 at 8:19 AM, Justin Schuh <jschuh@chromium.org> wrote: >> >> >> That seems most likely. This change just checks that TCMalloc's free-list >> pointers are valid (and right now it's turned on for debug builds only). If >> chunks in the free-list have invalid pointers, it almost certainly means >> that something is stepping on free chunks, or using them after being freed. >> >> Do you know if anyone has checked this under TSAN? It provides a lot more >> useful information for tracking these down after they've been verified. >> >> -j >> >> >
If that's still necessary, I can try the test under ASan and/or help you to do that. We've got an ASan buildbot running at http://build.chromium.org/p/chromium.fyi/waterfall?branch=&builder=ASAN+Build... and are going to push it to the main waterfall soon. But chances are that this particular test is not covered (e.g. if it has something to do with Views)
Message was sent while issue was closed.
Upstream gperftools maintainer here. I'm looking at list of differences between chromium fork and upstream and came across this set of changes. What is not clear to me from all comments is what is the purpose of this change? Is that for better/easier debugging ? Do you think it might be worth upstreaming it ?
I forget..but I think this was either debugging or for security hardening. jschuh@ or jar@ should know. I didn't review this one. On Sun, Oct 20, 2013 at 8:12 PM, <alkondratenko@gmail.com> wrote: > Upstream gperftools maintainer here. I'm looking at list of differences > between > chromium fork and upstream and came across this set of changes. What is not > clear to me from all comments is what is the purpose of this change? Is > that for > better/easier debugging ? Do you think it might be worth upstreaming it ? > > https://codereview.chromium.**org/7671034/<https://codereview.chromium.org/76... > To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org.
It was indeed both, if you consider "debugging" to include "easier to understand core dumps." A common problem was a memory corruption bug induced by a double free, (or by flat out memory corruption of the free heap? use after free? etc.). A double-free would routinely cause singly linked lists to be "crossed" (two lists point to the same "next" item). The fact that the single-linked-list also contained an external "list length" further aggravated the problem. This would generally explode when we either walked off the end of the list (paying too much attention to the length, such as when passing groups of memory from a central cache to the thread cache), or plausibly via a double use when reallocating (out of the separate thread caches <oops>). The addition of the back-pointers in a doubly linked list tend to reveal this instantly as we try to walk off the list. This avoids any chance of using the freed memory in two ways... adding (we think) a good amount of hardening. YMMV... but we didn't see any significant perf impact (in our application)... and we tend to get a much earlier crash when we do have corrupt heaps. As for upstream... you'd certainly want to carefully measure the perf impact in your application(s). The good news is that (as I recall) we crafted it to be easy to select between the two list implementations (at compile time, with no perf impact).... so that format may provide a nice upstream patch. Jim On Mon, Oct 21, 2013 at 11:45 AM, William Chan (陈智昌) <willchan@chromium.org>wrote: > I forget..but I think this was either debugging or for security hardening. > jschuh@ or jar@ should know. I didn't review this one. > > > On Sun, Oct 20, 2013 at 8:12 PM, <alkondratenko@gmail.com> wrote: > >> Upstream gperftools maintainer here. I'm looking at list of differences >> between >> chromium fork and upstream and came across this set of changes. What is >> not >> clear to me from all comments is what is the purpose of this change? Is >> that for >> better/easier debugging ? Do you think it might be worth upstreaming it ? >> >> https://codereview.chromium.**org/7671034/<https://codereview.chromium.org/76... >> > > To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org. |
