Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changes between Initial Version and Version 2 of Ticket #398


Ignore:
Timestamp:
2012-02-25T18:04:27Z (8 years ago)
Author:
Jakub Jermář
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #398

    • Property Keywords gsoc12 added
    • Property Milestone changed from 0.5.0 to 0.5.1
  • Ticket #398 – Description

    initial v2  
    11Improve the kernel's (and possibly also the uspace's) implementation of the generic hash table.
    22
    3 Unlike the current implementation, the new hash table should scale with the number of hashed items, i.e. the hash table should be able to grow/shrink as items are added to or removed from it. Implementation details of how this is achieved are not that important, with the following remarks:
     3 Details::
     4 The current HelenOS hash table implementation is very simple. It uses a predefined number of buckets and chaining of items. It is used in many places including the global page hash table, IRQ handling, generic range allocator, inter-process communication, device drivers, file systems and networking.
    45
    5   * the way the hash table is used should remain the same, i.e. use buckets with linked lists
    6   * number of links needed for an item to be hashed should remain 1, even though internally, there could be more instances of the hash table (e.g. for the old size and the new size)
    7   * the hash table needs to remain usable for the implementation of the global page hash table
    8   * insert should not break lockless find
     6 Unlike the current implementation, the new hash table should scale with the number of hashed items, i.e. the hash table should be able to grow/shrink as items are added to or removed from it. Implementation details of how this is achieved are not that important, with the following remarks:
     7
     8  - the way the hash table is used should remain the same, i.e. use buckets with linked lists
     9  - number of links needed for an item to be hashed should remain 1, even though internally, there could be more instances of the hash table (e.g. for the old size and the new size)
     10  - the hash table needs to remain usable for the implementation of the global page hash table
     11  - insert should not break lockless find operation of page table mappings
     12
     13 Integrating the new hash table with the current code shall be considered an integral part of the solution of this project.
     14
     15 What Gains and Benefits will this bring?::
     16  This will basically move us from using a poor-man's hash table implementation to using an advanced data structure with constant-time lookup operation. Given the key role of the hash table in various HelenOS subsystems, the benefit of realizing this project will be quite significant.
     17
     18 Difficulty::
     19  Medium to difficult. The solution needs to be able to work in the delicate environment of various kernel subsystems, especially with respect to synchronization.
     20
     21 Required skills::
     22  A successful applicant will have good skills of programming in the C language and will be familiar with advanced data structures. He or she will also need to be able to asses the synchronization needs of various hash table uses throughout the system.
     23
     24
     25 Documentation::
     26
     27 * [browser:/mainline/kernel/generic/src/adt/hash_table.c]
     28 * [http://en.wikipedia.org/wiki/Hash_table Hash table article on Wikipedia]
     29
     30 Possible mentors::
     31 HelenOS Core Team, Jakub Jermar