Page MenuHomeFreeBSD

dougm (Doug Moore)
User

Projects

User does not belong to any projects.

User Details

User Since
Jun 30 2017, 3:18 PM (169 w, 3 d)

Tauist. Bit twiddler. Advocate for continued logarithms.

Recent Activity

Tue, Sep 15

dougm added inline comments to D26424: Increase the vm_default max_user_wired value..
Tue, Sep 15, 8:31 AM

Wed, Sep 2

dougm accepted D26304: Avoid unnecessary object locking in vm_page_grab_pages_unlocked()..
Wed, Sep 2, 7:56 PM
dougm added inline comments to D26304: Avoid unnecessary object locking in vm_page_grab_pages_unlocked()..
Wed, Sep 2, 7:49 PM

Tue, Sep 1

dougm requested review of D26290: maintain a treap for vm_phys_segs, and use it for lookup.
Tue, Sep 1, 11:05 PM

Aug 24 2020

dougm accepted D26173: Permit vm_page_wire() for pages not belonging to an object..
Aug 24 2020, 8:02 PM
dougm added inline comments to D26173: Permit vm_page_wire() for pages not belonging to an object..
Aug 24 2020, 7:53 PM

Jul 25 2020

dougm committed rS363532: Fix an overflow bug in the blist allocator that needlessly capped max.
Fix an overflow bug in the blist allocator that needlessly capped max
Jul 25 2020, 6:29 PM
dougm closed D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.
Jul 25 2020, 6:29 PM

Jul 23 2020

dougm closed D25480: Change from red-black to wavl balancing for RB trees.
Jul 23 2020, 5:16 PM
dougm committed rS363450: Rank balanced (RB) trees are a class of balanced trees that includes.
Rank balanced (RB) trees are a class of balanced trees that includes
Jul 23 2020, 5:16 PM

Jul 22 2020

dougm added a comment to D25480: Change from red-black to wavl balancing for RB trees.

The code here has been tested and reviewed. I need to know that the man page is clear enough, and that the change itself isn't going to annoy a lot of people. A message to current a couple of weeks ago drew no response. Does anyone want to comment, favorably or unfavorably, or suggest who else ought to be consulted before this is checked in?

Jul 22 2020, 6:46 PM
dougm updated subscribers of D25480: Change from red-black to wavl balancing for RB trees.
Jul 22 2020, 6:44 PM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Copy a bit from the summary into the man page.

Jul 22 2020, 6:43 PM

Jul 21 2020

dougm updated the diff for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.

Update a comment.

Jul 21 2020, 5:34 PM
dougm updated subscribers of D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.
Jul 21 2020, 3:54 AM

Jul 20 2020

dougm updated the diff for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.

Reformat a comment. Change a couple of while loops into for loops.

Jul 20 2020, 9:09 PM
dougm updated the diff for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.

Remove a redundant assignment before a loop. Change a while loop to a for loop in blst_stats.

Jul 20 2020, 7:19 PM
dougm updated the diff for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.

Transform a loop in blst_next_leaf_alloc from while to do..while.

Jul 20 2020, 7:15 PM
dougm updated the summary of D25480: Change from red-black to wavl balancing for RB trees.
Jul 20 2020, 6:49 PM
dougm updated the diff for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.

Make suggested changes.

Jul 20 2020, 6:45 PM
dougm updated the summary of D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.
Jul 20 2020, 6:44 PM
dougm added a reviewer for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create: alc.
Jul 20 2020, 8:44 AM

Jul 19 2020

dougm updated the test plan for D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.
Jul 19 2020, 10:52 PM
dougm requested review of D25736: Avoid overflow in blist_create, remove swap pager checks before blist_create.
Jul 19 2020, 10:45 PM
dougm updated the summary of D25480: Change from red-black to wavl balancing for RB trees.
Jul 19 2020, 5:52 PM

Jul 18 2020

dougm updated the summary of D25480: Change from red-black to wavl balancing for RB trees.
Jul 18 2020, 10:34 PM

Jul 17 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Try to tighten up the introduction to rb trees in the manpage.

Jul 17 2020, 8:19 PM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Replace some manpage text with what alc has offered.

Jul 17 2020, 12:56 AM

Jul 16 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Endeavor to apply reviewer suggestions, with a briefer, punchier, less detailed paragraph on wavl trees.

Jul 16 2020, 7:25 PM

Jul 13 2020

dougm accepted D25650: Add vm_map_valid_range_KBI()..
Jul 13 2020, 4:14 PM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Make clear that red-black and avl trees also have rank-1 leaves.

Jul 13 2020, 12:08 AM

Jul 12 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Address more feedback on the manpage.

Jul 12 2020, 7:29 PM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Enforce the requirement that sentences in man pages must begin in column 1.

Jul 12 2020, 6:27 AM

Jul 11 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Offline, a reviewer has suggested that I improve the advocacy for wavl trees in the tree manpage, so I've attempted to do that.

Jul 11 2020, 10:51 PM

Jul 9 2020

dougm added a comment to D25480: Change from red-black to wavl balancing for RB trees.

R-B tree:
real 0m28.814s
user 0m28.795s

Jul 9 2020, 10:11 PM
dougm added a comment to D25480: Change from red-black to wavl balancing for RB trees.

I take it that this test does not do any lookups? I am personally not overly concerned by a pessimization in a write-heavy benchmark, since a binary search tree is probably not the best choice for that scenario to begin with.

Jul 9 2020, 9:22 PM
dougm added a comment to D25480: Change from red-black to wavl balancing for RB trees.

Adding a test result to reflect the downside of this change. If you replace the sorted inserts and removals with randomly generated ones (random() % maxsize), then the red-black tree takes this time:
real 0m19.819s
user 0m19.801s

Jul 9 2020, 7:22 PM

Jul 8 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Apply reviewer suggestions.

Jul 8 2020, 8:24 PM
dougm added a comment to D25480: Change from red-black to wavl balancing for RB trees.

For a test case that inserts and removes items in sorted order, so that the tree stays as unbalanced as possible, this modification improves performance from
real 0m20.837s
user 0m20.728s
to
real 0m16.141s
user 0m16.059s
and no color-balancing at all would be terrible.

Jul 8 2020, 9:39 AM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.
Jul 8 2020, 7:15 AM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Tighten up RB_REMOVE_COLOR a bit.

Jul 8 2020, 7:14 AM
dougm added a reviewer for D25480: Change from red-black to wavl balancing for RB trees: alc.
Jul 8 2020, 7:13 AM

Jun 30 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Optimize the color-changing code in RB_INSERT_COLOR and RB_REMOVE_COLOR by allowing both colors to be set to red, or not-red, at once, in some cases.

Jun 30 2020, 8:26 PM

Jun 28 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Move the handling of the deleting-a-leaf special coloring case from RB_REMOVE to RB_REMOVE_COLOR, to avoid entangling rebalancing with augmentation.

Jun 28 2020, 6:38 AM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Simplify RB_REMOVE. Let RB_REMOVE_COLOR do more of the color changing.

Jun 28 2020, 1:10 AM

Jun 27 2020

dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Add checking for null parent in RB_REMOVE.

Jun 27 2020, 5:50 PM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Restoring the missing tree.h changes.

Jun 27 2020, 6:31 AM
dougm updated the diff for D25480: Change from red-black to wavl balancing for RB trees.

Assuming that the failure to compile is because of the RB_AUGMENT call not within a loop, change to put it within a trivial loop. I've been testing with non-null augmentation so that this problem was not apparent.

Jun 27 2020, 6:14 AM
dougm added a comment to D25480: Change from red-black to wavl balancing for RB trees.

Oh, the irony. :)

Please give me a few days to read up on WAVL trees, I haven't encountered them before. (I know I usually take a few days anyway, sorry about that.)

Jun 27 2020, 12:17 AM

Jun 26 2020

dougm requested review of D25480: Change from red-black to wavl balancing for RB trees.
Jun 26 2020, 10:20 PM

Jun 25 2020

dougm committed rS362617: Eliminate the color field from the RB element struct. Identify the.
Eliminate the color field from the RB element struct. Identify the
Jun 25 2020, 5:44 PM
dougm closed D25418: Replace RB color field with tag bits in the parent pointer.
Jun 25 2020, 5:44 PM

Jun 24 2020

dougm updated the diff for D25418: Replace RB color field with tag bits in the parent pointer.

Apply reviewer suggestions.

Jun 24 2020, 7:52 PM
dougm updated the diff for D25418: Replace RB color field with tag bits in the parent pointer.

In RB_REMOVE_COLOR, treat the null parent-of-root as red, to avoid having the next iteration with a null parent pointer.

Jun 24 2020, 8:32 AM
dougm updated the diff for D25418: Replace RB color field with tag bits in the parent pointer.

Fixup RB_SET_PARENT after a hasty cut and paste.

Jun 24 2020, 6:18 AM

Jun 23 2020

dougm committed rS362562: In r362552, RB_SET_PARENT is defined, and use in parens in.
In r362552, RB_SET_PARENT is defined, and use in parens in
Jun 23 2020, 10:48 PM
dougm closed D25421: RB_SET_PARENT cannot be used as an expression.
Jun 23 2020, 10:48 PM
dougm requested review of D25421: RB_SET_PARENT cannot be used as an expression.
Jun 23 2020, 10:37 PM
dougm updated the diff for D25418: Replace RB color field with tag bits in the parent pointer.

Clean up RB_SET_PARENT.

Jun 23 2020, 8:16 PM
dougm requested review of D25418: Replace RB color field with tag bits in the parent pointer.
Jun 23 2020, 8:12 PM
dougm committed rS362552: Define RB_SET_PARENT to do all assignments to rb parent.
Define RB_SET_PARENT to do all assignments to rb parent
Jun 23 2020, 8:03 PM
dougm closed D25264: Define RB parent assignment macros.
Jun 23 2020, 8:03 PM
dougm closed D25245: strip color bit from rb tree pointers for linuxkpi.
Jun 23 2020, 3:21 AM
dougm requested review of D25245: strip color bit from rb tree pointers for linuxkpi.
Jun 23 2020, 3:21 AM
dougm updated the diff for D25204: Supply RB_COLOR macro.

Same change as before, from the right directory this time.

Jun 23 2020, 3:21 AM
dougm closed D25204: Supply RB_COLOR macro.
Jun 23 2020, 3:21 AM
dougm updated the diff for D25204: Supply RB_COLOR macro.

Include the root-of-tree case.

Jun 23 2020, 3:21 AM
dougm requested review of D25204: Supply RB_COLOR macro.
Jun 23 2020, 3:21 AM
dougm added a comment to D25264: Define RB parent assignment macros.

Let me give this a spin on Monday with a mellanox.

Jun 23 2020, 2:07 AM

Jun 20 2020

dougm committed rS362450: In concluding RB_REMOVE_COLOR, in the case when the sibling of the.
In concluding RB_REMOVE_COLOR, in the case when the sibling of the
Jun 20 2020, 8:26 PM
dougm closed D25335: Drop unneeded rotation from RB_REMOVE_COLOR.
Jun 20 2020, 8:26 PM
dougm added a comment to D25335: Drop unneeded rotation from RB_REMOVE_COLOR.

If I understand correctly, with the original code, the intermediate state of the tree prior to the second rotation after removing 7 is:

B6:17
    B5:11
        B4:6
            R2:2
Jun 20 2020, 6:51 PM
dougm added a reviewer for D25264: Define RB parent assignment macros: kib.
Jun 20 2020, 5:02 AM
dougm updated the summary of D25335: Drop unneeded rotation from RB_REMOVE_COLOR.
Jun 20 2020, 4:30 AM

Jun 19 2020

dougm abandoned D22777: clip within the subtree rooted at entry.
Jun 19 2020, 8:23 PM

Jun 18 2020

dougm accepted D25328: Add a helper function for validating VA ranges..
Jun 18 2020, 10:40 PM
dougm added a comment to D25328: Add a helper function for validating VA ranges..

See also vm_fault_quick_hold_pages in vm_fault.c.

Jun 18 2020, 5:25 PM
dougm added inline comments to D25328: Add a helper function for validating VA ranges..
Jun 18 2020, 5:17 PM
dougm updated the diff for D25335: Drop unneeded rotation from RB_REMOVE_COLOR.

Drop redundant assignments.

Jun 18 2020, 9:19 AM
dougm added a comment to D25335: Drop unneeded rotation from RB_REMOVE_COLOR.

A little test program. Enter a positive number to insert into the tree and a negative number to remove its inverse from the tree.

Jun 18 2020, 9:19 AM
dougm requested review of D25335: Drop unneeded rotation from RB_REMOVE_COLOR.
Jun 18 2020, 9:19 AM

Jun 16 2020

dougm accepted D25282: vm: Convert vm_map_clip_end from a macro to a regular inline function.
Jun 16 2020, 9:38 PM
dougm added inline comments to D25282: vm: Convert vm_map_clip_end from a macro to a regular inline function.
Jun 16 2020, 8:26 PM

Jun 14 2020

dougm updated the diff for D25264: Define RB parent assignment macros.

Take RB_SET_PARENT out of RB_SWAP_CHILD; it doesn't belong when the incoming child is NULL.

Jun 14 2020, 6:45 PM
dougm updated the diff for D25264: Define RB parent assignment macros.

Add a cast to (struct linux_root *).

Jun 14 2020, 9:02 AM
dougm updated the summary of D25264: Define RB parent assignment macros.
Jun 14 2020, 8:08 AM
dougm requested review of D25264: Define RB parent assignment macros.
Jun 14 2020, 7:57 AM

Jun 13 2020

dougm abandoned D25246: Clear the last bit from all the dereferenced rb_lefts and rb_rights .

Abandoning this.

Jun 13 2020, 4:03 AM
dougm committed rS362139: Linuxkpi uses the rb-tree structures without using their interfaces,.
Linuxkpi uses the rb-tree structures without using their interfaces,
Jun 13 2020, 1:54 AM
dougm closed D25250: Undo rb-tree changes incompatible with linuxkpi.
Jun 13 2020, 1:54 AM
dougm requested review of D25250: Undo rb-tree changes incompatible with linuxkpi.
Jun 13 2020, 12:14 AM

Jun 12 2020

dougm updated the diff for D25246: Clear the last bit from all the dereferenced rb_lefts and rb_rights .

Address some omissions in this patch before I abandon it.

Jun 12 2020, 11:16 PM
dougm updated the diff for D25246: Clear the last bit from all the dereferenced rb_lefts and rb_rights .

Don't modify 'new' in rb_replace_node.

Jun 12 2020, 7:19 PM
dougm requested review of D25246: Clear the last bit from all the dereferenced rb_lefts and rb_rights .
Jun 12 2020, 7:06 PM
dougm committed rS362110: Revert r362108, as it breaks compilation..
Revert r362108, as it breaks compilation.
Jun 12 2020, 5:48 PM
dougm committed rS362108: The linuxkpi code accesses left/right rb tree pointers without using.
The linuxkpi code accesses left/right rb tree pointers without using
Jun 12 2020, 4:52 PM
dougm updated the summary of D25245: strip color bit from rb tree pointers for linuxkpi.
Jun 12 2020, 4:40 PM
dougm added a reviewer for D25245: strip color bit from rb tree pointers for linuxkpi: alc.
Jun 12 2020, 4:39 PM

Jun 10 2020

dougm committed rS362000: Fixup r361997 by balancing parens. Duh..
Fixup r361997 by balancing parens. Duh.
Jun 10 2020, 3:36 AM
dougm committed rS361997: Restore an RB_COLOR macro, for the benefit of a bit of DIAGNOSTIC code.
Restore an RB_COLOR macro, for the benefit of a bit of DIAGNOSTIC code
Jun 10 2020, 2:50 AM