]> git.proxmox.com Git - mirror_spl-debian.git/commit
Track emergency object in rbtree
authorBrian Behlendorf <behlendorf1@llnl.gov>
Tue, 30 Oct 2012 17:45:50 +0000 (10:45 -0700)
committerBrian Behlendorf <behlendorf1@llnl.gov>
Tue, 6 Nov 2012 22:54:19 +0000 (14:54 -0800)
commited3163484d2e70df8d9c50bad9678891b26c0fa0
tree874c4b05a1133afdf9503df3f1a34e300193b6b3
parent165f13c33abadc06ccaea1c4f654fddfa316a80f
Track emergency object in rbtree

In the initial implementation emergency objects were tracked on a
per-cache list.  The assumption was that under normal operation we
would never allocate more than a handful of these objects.  So the
cost of walking the list during free was expected to be negligible.

However real world usage has shown that emergency objects tend to
be allocated in batches.  A deadlock will be detected and several
thousand emergency objects will be allocated before the original
blocked slab allocation can complete.

Therefore the original list has been replaced by a red black tree
which is sorted by the memory address of each allocated object.
This bounds the worst case insertion and removal time to O(log n)
which minimize contention on the assoicated spin lock.

Signed-off-by: Brian Behlendorf <behlendorf1@llnl.gov>
include/sys/kmem.h
module/spl/spl-kmem.c