Annotation of wikisrc/projects/project/atomic_radix_patricia_trees.mdwn, revision 1.1

1.1     ! jmmv        1: [[!template id=project
        !             2: 
        !             3: title="Lockless, atomic and generic Radix/Patricia trees"
        !             4: 
        !             5: contact="""
        !             6: [tech-kern](mailto:tech-kern@NetBSD.org),
        !             7: [board](mailto:board@NetBSD.org),
        !             8: [core](mailto:core@NetBSD.org)
        !             9: """
        !            10: 
        !            11: category="kernel"
        !            12: difficulty="hard"
        !            13: funded="The NetBSD Foundation"
        !            14: 
        !            15: description="""
        !            16: This project proposal is a subtask of [[smp_networking]] and is elegible
        !            17: for funding independently.
        !            18: 
        !            19: The goal of this project is to implement lockless, atomic and generic Radix
        !            20: and Patricia trees.  BSD systems have always used a radix tree for their
        !            21: routing tables.  However, the radix tree implementation is showing its age.
        !            22: Its lack of flexibility (it is only suitable for use in a routing table)
        !            23: and overhead of use (requires memory allocation/deallocation for insertions
        !            24: and removals) make replacing it with something better tuned to today's
        !            25: processors a necessity.
        !            26: 
        !            27: Since a radix tree branches on bit differences, finding these bit
        !            28: differences efficiently is crucial to the speed of tree operations.  This
        !            29: is most quickly done by XORing the key and the tree node's value together
        !            30: and then counting the number of leading zeroes in the result of the XOR.
        !            31: Many processors today (ARM, PowerPC) have instructions that can count the
        !            32: number of leading zeroes in a 32 bit word (and even a 64 bit word).  Even
        !            33: those that do not can use a simple constant time routine to count them:
        !            34: 
        !            35:     int
        !            36:     clz(unsigned int bits)
        !            37:     {
        !            38:         int zeroes = 0;
        !            39:         if (bits == 0)
        !            40:             return 32;
        !            41:         if (bits & 0xffff0000) bits &= 0xffff0000; else zeroes += 16;
        !            42:         if (bits & 0xff00ff00) bits &= 0xff00ff00; else zeroes += 8;
        !            43:         if (bits & 0xf0f0f0f0) bits &= 0xf0f0f0f0; else zeroes += 4;
        !            44:         if (bits & 0xcccccccc) bits &= 0xcccccccc; else zeroes += 2;
        !            45:         if (bits & 0xaaaaaaaa) bits &= 0xaaaaaaaa; else zeroes += 1;
        !            46:         return zeroes;
        !            47:     }
        !            48: 
        !            49: The existing BSD radix tree implementation does not use this method but
        !            50: instead uses a far more expensive method of comparision.  Adapting the
        !            51: existing implementation to do the above is actually more expensive than
        !            52: writing a new implementation.
        !            53: 
        !            54: The primary requirements for the new radix tree are:
        !            55: 
        !            56: * Be self-contained.  It cannot require additional memory other than what
        !            57:   is used in its data structures.
        !            58: 
        !            59: * Be generic.  A radix tree has uses outside networking.
        !            60: 
        !            61: To make the radix tree flexible, all knowledge of how keys are represented
        !            62: has to be encapsulated into a `pt_tree_ops_t` structure with these
        !            63: functions:
        !            64: 
        !            65: * `bool ptto_matchnode(const void *foo, const void *bar, pt_bitoff_t
        !            66:   max_bitoff, pt_bitoff_t *bitoffp, pt_slot_t *slotp);`
        !            67: 
        !            68:   Returns true if both `foo` and `bar` objects have the identical string of
        !            69:   bits starting at `*bitoffp` and ending before `max_bitoff`.  In addition
        !            70:   to returning true, `*bitoffp` should be set to the smaller of
        !            71:   `max_bitoff` or the length, in bits, of the compared bit strings.  Any
        !            72:   bits before `*bitoffp` are to be ignored.  If the string of bits are not
        !            73:   identical, `*bitoffp` is set to the where the bit difference occured,
        !            74:   `*slotp` is the value of that bit in `foo`, and false is returned.  The
        !            75:   `foo` and `bar` (if not `NULL`) arguments are pointers to a key member
        !            76:   inside a tree object.  If bar is `NULL`, then assume it points to a key
        !            77:   consisting of entirely of zero bits.
        !            78: 
        !            79: * `bool ptto_matchkey(const void *key, const void *node_key,
        !            80:   pt_bitoff_t bitoff, pt_bitlen_t bitlen);`
        !            81: 
        !            82:   Returns true if both `key` and `node_key` objects have identical strings
        !            83:   of `bitlen` bits starting at `bitoff`.  The `key` argument is the same
        !            84:   key argument supplied to `ptree_find_filtered_node`.
        !            85: 
        !            86: * `pt_slot_t ptto_testnode(const void *node_key, pt_bitoff_t bitoff,
        !            87:   pt_bitlen_t bitlen);`
        !            88: 
        !            89:   Returns `bitlen` bits starting at `bitoff` from `node_key`.  The
        !            90:   `node_key` argument is a pointer to the key members inside a tree object.
        !            91: 
        !            92: * `pt_slot_t ptto_testkey(const void *key, pt_bitoff_t bitoff,
        !            93:   pt_bitlen_t bitlen);`
        !            94: 
        !            95:   Returns `bitlen` bits starting at `bitoff` from key.  The `key` argument
        !            96:   is the same key argument supplied to `ptree_find_filtered_node`.
        !            97: 
        !            98: All bit offsets are relative to the most significant bit of the key,
        !            99: 
        !           100: The ptree programming interface should contains these routines:
        !           101: 
        !           102: * `void ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops, size_t
        !           103:   ptnode_offset, size_t key_offset);`
        !           104: 
        !           105:   Initializes a ptree.  If `pt` points at an existing ptree, all knowledge
        !           106:   of that ptree is lost.  The `pt` argument is a pointer to the `pt_tree_t`
        !           107:   to be initialized.  The `ops` argument is a pointer to the
        !           108:   `pt_tree_ops_t` used by the ptree.  This has four members: The
        !           109:   `ptnode_offset` argument contains the offset from the beginning of an
        !           110:   item to its `pt_node_t` member.  The `key_offset` argument contains the
        !           111:   offset from the beginning of an item to its key data.  This is used if 0
        !           112:   is used, a pointer to the beginning of the item will be generated.
        !           113: 
        !           114: * `void *ptree_find_filtered_node(pt_tree_t *pt, const void *key,
        !           115:   pt_filter_t filter, void *filter_ctx);`
        !           116: 
        !           117:   The filter argument is either `NULL` or a function `bool (*)(const
        !           118:   void *, void *, int);`
        !           119: 
        !           120: * `bool ptree_insert_mask_node(pt_tree_t *pt, void *item, pt_bitlen_t
        !           121:   masklen);`
        !           122: 
        !           123: * `bool ptree_insert_node(pt_tree_t *pt, void *item);`
        !           124: 
        !           125: * `void *ptree_iterate(pt_tree_t *pt, const void *node, pt_direction_t
        !           126:   direction);`
        !           127: 
        !           128: * `void ptree_remove_node(pt_tree_t *pt, const pt_tree_ops_t *ops,
        !           129:   void *item);`
        !           130: """
        !           131: ]]
        !           132: 
        !           133: [[!tag smp_networking]]

CVSweb for NetBSD wikisrc <wikimaster@NetBSD.org> software: FreeBSD-CVSweb