Hi everybody,
Goals
-----
The goal of my project was to create a scalable resizable
concurrent hash table:
- scalable = adding CPUs speeds it up.
- resizable = it grows (and shrinks) depending on the number
of items in the table.
- concurrent = allows parallel access from different cpus.
As part of my project I was to replace the previous simple
non-resizable kernel hash table used in the page hash table
and the futex subsystem with the new one.
What is more, I noted in my project proposal that HelenOS
would benefit from my work: First, the performance of core
kernel function would improve (mainly page hash table).
Second, adding RCU would allow future interesting
functionality.
Completed Work
--------------
The work resulted in:
- Two working RCU implementations/algorithms
- A concurrent hash table (CHT)
- Improved user space hash table that now resizes, avoids
bad hashes and is better suited for future changes.
- Automated tests of both RCU and CHT
- Benchmarks of both RCU and CHT
- A couple of bug fixes due to a review of some of the
existing code.
- A work queue including tests
- A facility to call functions on other cpus including tests
Goals not fulfilled
-------------------
CHT had not been integrated into the kernel, ie it has
not replaced the global page hash table and it has not
been utilized in the futex subsystem.
What is more, the lack of an implementation of atomic_cas_ptr()
for architectures other than ia32 and amd64 implies CHT
cannot currently be used on those architectures.
Assessment
----------
The main aim was to create a CHT and it had been
implemented. The implemented CHT however requires
an atomic_cas_ptr() to be added to archs other than
ia32, amd64, which currently limits its use. The
difficulty of adding that one function to other archs
depends on one's familiarity with the particular arch.
It is typically implemented as a single instruction,
but it is necessary to ensure certain memory ordering
guarantees so a simple copy&paste from the instruction
manual will not do.
The secondary goal was to improve HelenOS's performance
by switching the global page hash table to CHT. While
the GPHT was not converted to use CHT, HelenOS's performance
and memory consumption was improved across the board
by changing the user space hash table implementation.
Firstly, it resizes; therefore, one no longer has to
make wild guesses about its size. Secondly, I replaced
suboptimal hash functions with sound alternatives.
Thirdly, I refactored the interface which makes the
table's implementation easy to change (see [1] what
this trivial change entails in terms of files and LOC
affected). Whereas a trivial change such as switching
the collision chain representation from a double linked
to a single linked list (in order to further reduce
memory usage) would have been an enormous feat before,
it is now as simple as it gets thanks to the refactored
interface. Lastly, it is important to understand that
most (if not all) users of the user space hash table
are single-threaded and, therefore, cannot benefit from
CHT whatsoever (namely its scalability and concurrency).
The last proposed benefit of my work was to implement
RCU. The repository contains two.
Future work
-----------
RCU is interrupt safe but it is not non-maskable
interrupt safe. I have already commented placed
in the code where changes are necessary. The changes
require an atomic_set_return_local() for each architecture.
IPIs have to be made to work on architectures beside ia32
and amd64 in a SMP build in order for smp calls to work
(and transitively also RCU). This mean sparc64.
Adam
[1] http://bazaar.launchpad.net/~adam-hraska+lp/helenos/rcu/revision/1589
_______________________________________________
HelenOS-devel mailing list
[email protected]
http://lists.modry.cz/cgi-bin/listinfo/helenos-devel
