[lkml]   [2012]   [Mar]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRE: RFC: memory leak in udp_table_init

    > > The pid table is a good example of something where a hash
    > > table is unnecessary.
    > > Linux should steal the code I put into NetBSD :-)
    > On this unrelated topic. What algorithm did you use on NetBSD for
    > dealing with pids?

    Basically I forced the hash chain length to one by allocating
    a pid that hit an empty entry in the table.

    So you start off with (say) 64 entries and use the low 6
    bits to index the table. The higher bits are incremented
    each time a 'slot' is reused.
    Free entries are kept in a FIFO list.
    So each entry either contains a pointer to the process,
    or the high bits and the index of the next free slot.
    (and the PGID pointer).
    When there are only (say) 2 free entries, then the table
    size is doubled, the pointers moved to the correct places,
    the free ist fixed up, and the minimum number of free entries

    The overall effect:
    - lookup is only ever a mask and index + compare.
    - Allocate is always fast and fixed cost (except when
    the table size has to be doubled).
    - A pid value will never be reused within (about) 2000
    allocates (for 16bit pids, much larger for 32bit ones).
    - Allocated pid numbers tend to be random, certainly
    very difficult to predict.
    - Small memory footprint for small systems.
    For pids we normally avoid issuing large values, but
    will do so to avoid immediate re-use on systems that
    have 1000s of active processes.

    See lines 580-820 of


     \ /
      Last update: 2012-03-01 09:57    [W:0.022 / U:3.520 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site