<div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div>Hi Jason, <br><br>Thank you so much for the reply. I read the code once again, but I still don't understand the calculations here.<br>The original dirty chunk cmp function is,<br><br>static inline int<br>arena_chunk_dirty_comp(arena_chunk_t *a, arena_chunk_t *b)<br>{<br> ......<br> size_t a_val = (a->nruns_avail - a->nruns_adjac) *<br> b->nruns_avail;<br> size_t b_val = (b->nruns_avail - b->nruns_adjac) *<br> a->nruns_avail;<br><br> if (a_val < b_val)<br> return (1);<br> if (a_val > b_val)<br> return (-1);<br></div><div> ......<br>}<br><br>In the case as we mentioned above, how do you get a_val = 0.45 and b_val = 1.5?<br>Is it because a_val = (10 - 1) / 20; b_val = (20 - 5) / 10?<br>But according to the code, a_val = (10 - 1) * 20, and b_val = (20 - 5) * 10, so it should return (-1)?<br><br>And I trace the code in a demo, that makes me more confusing...<br>At first, I set the breakpoint at arena_chunk_dirty_first() when the Je is performing purging, and the backtrace is like this,<br>#0 arena_chunk_dirty_first (rbtree=0x7ffff7010110) at src/arena.c:171<br>#1 0x0000000000411f4e in arena_purge (arena=0x7ffff7010080, all=false) at src/arena.c:1032<br>#2 0x0000000000411447 in arena_maybe_purge (arena=0x7ffff7010080) at src/arena.c:793<br>#3 0x000000000041299f in arena_run_dalloc (arena=0x7ffff7010080, run=0x7ffff68ce000, dirty=true, cleaned=false) at src/arena.c:1232<br>#4 0x0000000000414db4 in je_arena_dalloc_large_locked (arena=0x7ffff7010080, chunk=0x7ffff6800000, ptr=0x7ffff68ce000) at src/arena.c:1971<br>#5 0x0000000000414df6 in je_arena_dalloc_large (arena=0x7ffff7010080, chunk=0x7ffff6800000, ptr=0x7ffff68ce000) at src/arena.c:1979<br>#6 0x0000000000409914 in je_arena_dalloc (arena=0x7ffff7010080, chunk=0x7ffff6800000, ptr=0x7ffff68ce000, try_tcache=true)<br> at include/jemalloc/internal/arena.h:1056<br>#7 0x0000000000401b85 in je_idalloct (ptr=0x7ffff68ce000, try_tcache=true) at include/jemalloc/internal/jemalloc_internal.h:898<br>#8 0x0000000000401c06 in je_iqalloct (ptr=0x7ffff68ce000, try_tcache=true) at include/jemalloc/internal/jemalloc_internal.h:917<br>#9 0x0000000000401c25 in je_iqalloc (ptr=0x7ffff68ce000) at include/jemalloc/internal/jemalloc_internal.h:924<br>#10 0x0000000000405414 in ifree (ptr=0x7ffff68ce000) at src/jemalloc.c:1233<br>#11 0x0000000000405a5c in xffree (ptr=0x7ffff68ce000) at src/jemalloc.c:1308<br>#12 0x00000000004011f1 in main (argc=1, argv=0x7fffffffe0c8) at main.c:40<br><br>We can see the dirty chuck tree, <br>(gdb) p (arena_chunk_tree_t) *0x7ffff7010110<br>$16 = {<br> rbt_root = 0x7ffff6800000, <br> rbt_nil = {<br> arena = 0x0, <br> dirty_link = {<br> rbn_left = 0x7ffff7010118, <br> rbn_right_red = 0x7ffff7010118<br> }, <br> ndirty = 0, <br> nruns_avail = 0, <br> nruns_adjac = 0, <br> map = {{<br> ......<br> }}<br> }<br>}<br><br>The root node is 0x7ffff6800000,<br>(gdb) p (arena_chunk_t) *0x7ffff6800000<br>$17 = {<br> arena = 0x7ffff7010080, <br> dirty_link = {<br> rbn_left = 0x7ffff6c00000, <br> rbn_right_red = 0x7ffff7010118<br> }, <br> ndirty = 96, <br> nruns_avail = 3, <br> nruns_adjac = 1, <br> map = {{<br> ......<br> }}<br>}<br><br>And the left node is 0x7ffff6c00000, which is also the left-most node(we only have two chunks here),<br>(gdb) p (arena_chunk_t) *0x7ffff6c00000<br>$18 = {<br> arena = 0x7ffff7010080, <br> dirty_link = {<br> rbn_left = 0x7ffff7010118, <br> rbn_right_red = 0x7ffff7010119<br> }, <br> ndirty = 72, <br> nruns_avail = 127, <br> nruns_adjac = 0, <br> map = {{<br> ......<br> }}<br>}<br><br>So when returned from frame#0, we got the chunk 0x7ffff6c00000,<br>(gdb) fin<br>Run till exit from #0 arena_chunk_dirty_first (rbtree=0x7ffff7010110) at src/arena.c:171<br>0x0000000000411f4e in arena_purge (arena=0x7ffff7010080, all=false) at src/arena.c:1032<br>1032 chunk = arena_chunk_dirty_first(&arena->chunks_dirty);<br>Value returned is $19 = (arena_chunk_t *) 0x7ffff6c00000<br><br>That is the traversal order, from 0x7ffff6c00000 -> 0x7ffff6800000. But you can see the <br>node 0x7ffff6c00000 with nruns_avail = 127, nruns_adjac = 0; and 0x7ffff6800000<br>with nruns_avail = 3, nruns_adjac = 1. So why? According to the algorithm as you said,<br>shoultn't we purge 0x7ffff6800000 first? However actually we purged a chunk even with no<br>adjac first!<br><br><br></div><br><br>在 2016-01-12 03:37:23，"Jason Evans" <jasone@canonware.com> 写道：<br> <blockquote id="isReplyContent" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">On Jan 7, 2016, at 6:46 PM, mmzsmm <<a href="mailto:mmzsmm@163.com" class="">mmzsmm@163.com</a>> wrote:<div><blockquote type="cite" class=""><div class=""><div style="line-height: 1.7; font-size: 14px; font-family: Arial;" class=""><div class="">[...] according to the code comments, the clean-dirty fragmentation is measured as,<br class=""><br class="">* Order such that chunks with higher fragmentation are "less than"<br class="">* those with lower fragmentation -- purging order is from "least" to<br class="">* "greatest". <br class=""> mean current avail run size nruns_avail-nruns_adjac<br class="">-------------------------------------------- = ----------------------------------<br class="">mean defragmented avail run size nruns_avail<br class=""><br class="">So if I have a chunkA with avail_runs = 10, adjac = 1, and another chunkB with avail_runs = 20, adjac = 5.<br class="">Obviously, the fragmentA(0.9) > fragmentB(0.75), so the A will be prior to B in the dirty chunk tree, and <br class="">will be purged first. But the chunkB truely has more adjacs than the A, and the performace gain after purging <br class="">chunkA is also less than the other(0.1 vs 0.25). Why we prefer to purge the chunk with "less adjacs"? <br class="">Shouldn't we purge more adjacs or clean-dirty fragments to acquire more continuous unalloc pages?<br class=""></div></div></div></blockquote><div><br class=""></div><div>We actually do purge B first, but it's hard to see unless you follow the calculations in the code. Note that a_val=0.45 and b_val=1.5 in this case, which means that the comparison function returns 1, causing A to come after B in the in-order tree traversal.</div><br class=""><blockquote type="cite" class=""><div class=""><div style="line-height: 1.7; font-size: 14px; font-family: Arial;" class=""><div class="">Another question is, I notice that before the git node e3d13060 there are two avail-trees, one is for dirty, <br class="">and another for clean,<br class=""> arena_avail_tree_t runs_avail_clean;<br class=""> arena_avail_tree_t runs_avail_dirty;<br class="">After that, the two became one. So how to ensure the new runs allocaction to prefer to dirty pages? <br class=""></div></div></div></blockquote><div><br class=""></div><div>IIRC, there were versions of jemalloc that did not prefer dirty pages.</div><div><br class=""></div><div>Note that you're looking at jemalloc 3.x code, but 4.x uses substantially different algorithms that obsoleted the code that ordered chunks according to fragmentation.</div><div><br class=""></div><div>Jason</div></div></blockquote></div><br><br><span title="neteasefooter"><p> </p></span>