From d68c6810e2b7b5e9feed2b8af8a84cb1b4ce744d Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 9 Mar 2012 13:09:18 -0500 Subject: [PATCH] RCU judy array: implement node get functions Signed-off-by: Mathieu Desnoyers --- rcuja/bitfield.h | 397 +++++++++++++++++++++++++++++++++++++++++++++++ rcuja/endian.h | 34 ++++ rcuja/rcuja.c | 316 +++++++++++++++++++++++++++++++++---- urcu/compiler.h | 2 + 4 files changed, 722 insertions(+), 27 deletions(-) create mode 100644 rcuja/bitfield.h create mode 100644 rcuja/endian.h diff --git a/rcuja/bitfield.h b/rcuja/bitfield.h new file mode 100644 index 0000000..1906a97 --- /dev/null +++ b/rcuja/bitfield.h @@ -0,0 +1,397 @@ +#ifndef _URCU_RCUJA_BITFIELD_H +#define _URCU_RCUJA_BITFIELD_H + +/* + * Bitfields read/write functions. + * + * Copyright 2010 - Mathieu Desnoyers + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + */ + +#include /* C99 5.2.4.2 Numerical limits */ +#include /* C99 5.2.4.2 Numerical limits */ +#include +#include "endian.h" /* Non-standard BIG_ENDIAN, LITTLE_ENDIAN, BYTE_ORDER */ + +/* We can't shift a int from 32 bit, >> 32 and << 32 on int is undefined */ +#define _ja_piecewise_rshift(_v, _shift) \ +({ \ + typeof(_v) ___v = (_v); \ + typeof(_shift) ___shift = (_shift); \ + unsigned long sb = (___shift) / (sizeof(___v) * CHAR_BIT - 1); \ + unsigned long final = (___shift) % (sizeof(___v) * CHAR_BIT - 1); \ + \ + for (; sb; sb--) \ + ___v >>= sizeof(___v) * CHAR_BIT - 1; \ + ___v >>= final; \ +}) + +#define _ja_piecewise_lshift(_v, _shift) \ +({ \ + typeof(_v) ___v = (_v); \ + typeof(_shift) ___shift = (_shift); \ + unsigned long sb = (___shift) / (sizeof(___v) * CHAR_BIT - 1); \ + unsigned long final = (___shift) % (sizeof(___v) * CHAR_BIT - 1); \ + \ + for (; sb; sb--) \ + ___v <<= sizeof(___v) * CHAR_BIT - 1; \ + ___v <<= final; \ +}) + +#define _ja_is_signed_type(type) (((type)(-1)) < 0) + +#define _ja_unsigned_cast(type, v) \ +({ \ + (sizeof(v) < sizeof(type)) ? \ + ((type) (v)) & (~(~(type) 0 << (sizeof(v) * CHAR_BIT))) : \ + (type) (v); \ +}) + +/* + * ja_bitfield_write - write integer to a bitfield in native endianness + * + * Save integer to the bitfield, which starts at the "start" bit, has "len" + * bits. + * The inside of a bitfield is from high bits to low bits. + * Uses native endianness. + * For unsigned "v", pad MSB with 0 if bitfield is larger than v. + * For signed "v", sign-extend v if bitfield is larger than v. + * + * On little endian, bytes are placed from the less significant to the most + * significant. Also, consecutive bitfields are placed from lower bits to higher + * bits. + * + * On big endian, bytes are places from most significant to less significant. + * Also, consecutive bitfields are placed from higher to lower bits. + */ + +#define _ja_bitfield_write_le(_ptr, type, _start, _length, _v) \ +do { \ + typeof(_v) __v = (_v); \ + type *__ptr = (void *) (_ptr); \ + unsigned long __start = (_start), __length = (_length); \ + type mask, cmask; \ + unsigned long ts = sizeof(type) * CHAR_BIT; /* type size */ \ + unsigned long start_unit, end_unit, this_unit; \ + unsigned long end, cshift; /* cshift is "complement shift" */ \ + \ + if (!__length) \ + break; \ + \ + end = __start + __length; \ + start_unit = __start / ts; \ + end_unit = (end + (ts - 1)) / ts; \ + \ + /* Trim v high bits */ \ + if (__length < sizeof(__v) * CHAR_BIT) \ + __v &= ~((~(typeof(__v)) 0) << __length); \ + \ + /* We can now append v with a simple "or", shift it piece-wise */ \ + this_unit = start_unit; \ + if (start_unit == end_unit - 1) { \ + mask = ~((~(type) 0) << (__start % ts)); \ + if (end % ts) \ + mask |= (~(type) 0) << (end % ts); \ + cmask = (type) __v << (__start % ts); \ + cmask &= ~mask; \ + __ptr[this_unit] &= mask; \ + __ptr[this_unit] |= cmask; \ + break; \ + } \ + if (__start % ts) { \ + cshift = __start % ts; \ + mask = ~((~(type) 0) << cshift); \ + cmask = (type) __v << cshift; \ + cmask &= ~mask; \ + __ptr[this_unit] &= mask; \ + __ptr[this_unit] |= cmask; \ + __v = _ja_piecewise_rshift(__v, ts - cshift); \ + __start += ts - cshift; \ + this_unit++; \ + } \ + for (; this_unit < end_unit - 1; this_unit++) { \ + __ptr[this_unit] = (type) __v; \ + __v = _ja_piecewise_rshift(__v, ts); \ + __start += ts; \ + } \ + if (end % ts) { \ + mask = (~(type) 0) << (end % ts); \ + cmask = (type) __v; \ + cmask &= ~mask; \ + __ptr[this_unit] &= mask; \ + __ptr[this_unit] |= cmask; \ + } else \ + __ptr[this_unit] = (type) __v; \ +} while (0) + +#define _ja_bitfield_write_be(_ptr, type, _start, _length, _v) \ +do { \ + typeof(_v) __v = (_v); \ + type *__ptr = (void *) (_ptr); \ + unsigned long __start = (_start), __length = (_length); \ + type mask, cmask; \ + unsigned long ts = sizeof(type) * CHAR_BIT; /* type size */ \ + unsigned long start_unit, end_unit, this_unit; \ + unsigned long end, cshift; /* cshift is "complement shift" */ \ + \ + if (!__length) \ + break; \ + \ + end = __start + __length; \ + start_unit = __start / ts; \ + end_unit = (end + (ts - 1)) / ts; \ + \ + /* Trim v high bits */ \ + if (__length < sizeof(__v) * CHAR_BIT) \ + __v &= ~((~(typeof(__v)) 0) << __length); \ + \ + /* We can now append v with a simple "or", shift it piece-wise */ \ + this_unit = end_unit - 1; \ + if (start_unit == end_unit - 1) { \ + mask = ~((~(type) 0) << ((ts - (end % ts)) % ts)); \ + if (__start % ts) \ + mask |= (~((type) 0)) << (ts - (__start % ts)); \ + cmask = (type) __v << ((ts - (end % ts)) % ts); \ + cmask &= ~mask; \ + __ptr[this_unit] &= mask; \ + __ptr[this_unit] |= cmask; \ + break; \ + } \ + if (end % ts) { \ + cshift = end % ts; \ + mask = ~((~(type) 0) << (ts - cshift)); \ + cmask = (type) __v << (ts - cshift); \ + cmask &= ~mask; \ + __ptr[this_unit] &= mask; \ + __ptr[this_unit] |= cmask; \ + __v = _ja_piecewise_rshift(__v, cshift); \ + end -= cshift; \ + this_unit--; \ + } \ + for (; (long) this_unit >= (long) start_unit + 1; this_unit--) { \ + __ptr[this_unit] = (type) __v; \ + __v = _ja_piecewise_rshift(__v, ts); \ + end -= ts; \ + } \ + if (__start % ts) { \ + mask = (~(type) 0) << (ts - (__start % ts)); \ + cmask = (type) __v; \ + cmask &= ~mask; \ + __ptr[this_unit] &= mask; \ + __ptr[this_unit] |= cmask; \ + } else \ + __ptr[this_unit] = (type) __v; \ +} while (0) + +/* + * ja_bitfield_write - write integer to a bitfield in native endianness + * ja_bitfield_write_le - write integer to a bitfield in little endian + * ja_bitfield_write_be - write integer to a bitfield in big endian + */ + +#if (BYTE_ORDER == LITTLE_ENDIAN) + +#define ja_bitfield_write(ptr, type, _start, _length, _v) \ + _ja_bitfield_write_le(ptr, type, _start, _length, _v) + +#define ja_bitfield_write_le(ptr, type, _start, _length, _v) \ + _ja_bitfield_write_le(ptr, type, _start, _length, _v) + +#define ja_bitfield_write_be(ptr, type, _start, _length, _v) \ + _ja_bitfield_write_be(ptr, unsigned char, _start, _length, _v) + +#elif (BYTE_ORDER == BIG_ENDIAN) + +#define ja_bitfield_write(ptr, type, _start, _length, _v) \ + _ja_bitfield_write_be(ptr, type, _start, _length, _v) + +#define ja_bitfield_write_le(ptr, type, _start, _length, _v) \ + _ja_bitfield_write_le(ptr, unsigned char, _start, _length, _v) + +#define ja_bitfield_write_be(ptr, type, _start, _length, _v) \ + _ja_bitfield_write_be(ptr, type, _start, _length, _v) + +#else /* (BYTE_ORDER == PDP_ENDIAN) */ + +#error "Byte order not supported" + +#endif + +#define _ja_bitfield_read_le(_ptr, type, _start, _length, _vptr) \ +do { \ + typeof(*(_vptr)) *__vptr = (_vptr); \ + typeof(*__vptr) __v; \ + type *__ptr = (void *) (_ptr); \ + unsigned long __start = (_start), __length = (_length); \ + type mask, cmask; \ + unsigned long ts = sizeof(type) * CHAR_BIT; /* type size */ \ + unsigned long start_unit, end_unit, this_unit; \ + unsigned long end, cshift; /* cshift is "complement shift" */ \ + \ + if (!__length) { \ + *__vptr = 0; \ + break; \ + } \ + \ + end = __start + __length; \ + start_unit = __start / ts; \ + end_unit = (end + (ts - 1)) / ts; \ + \ + this_unit = end_unit - 1; \ + if (_ja_is_signed_type(typeof(__v)) \ + && (__ptr[this_unit] & ((type) 1 << ((end % ts ? : ts) - 1)))) \ + __v = ~(typeof(__v)) 0; \ + else \ + __v = 0; \ + if (start_unit == end_unit - 1) { \ + cmask = __ptr[this_unit]; \ + cmask >>= (__start % ts); \ + if ((end - __start) % ts) { \ + mask = ~((~(type) 0) << (end - __start)); \ + cmask &= mask; \ + } \ + __v = _ja_piecewise_lshift(__v, end - __start); \ + __v |= _ja_unsigned_cast(typeof(__v), cmask); \ + *__vptr = __v; \ + break; \ + } \ + if (end % ts) { \ + cshift = end % ts; \ + mask = ~((~(type) 0) << cshift); \ + cmask = __ptr[this_unit]; \ + cmask &= mask; \ + __v = _ja_piecewise_lshift(__v, cshift); \ + __v |= _ja_unsigned_cast(typeof(__v), cmask); \ + end -= cshift; \ + this_unit--; \ + } \ + for (; (long) this_unit >= (long) start_unit + 1; this_unit--) { \ + __v = _ja_piecewise_lshift(__v, ts); \ + __v |= _ja_unsigned_cast(typeof(__v), __ptr[this_unit]);\ + end -= ts; \ + } \ + if (__start % ts) { \ + mask = ~((~(type) 0) << (ts - (__start % ts))); \ + cmask = __ptr[this_unit]; \ + cmask >>= (__start % ts); \ + cmask &= mask; \ + __v = _ja_piecewise_lshift(__v, ts - (__start % ts)); \ + __v |= _ja_unsigned_cast(typeof(__v), cmask); \ + } else { \ + __v = _ja_piecewise_lshift(__v, ts); \ + __v |= _ja_unsigned_cast(typeof(__v), __ptr[this_unit]);\ + } \ + *__vptr = __v; \ +} while (0) + +#define _ja_bitfield_read_be(_ptr, type, _start, _length, _vptr) \ +do { \ + typeof(*(_vptr)) *__vptr = (_vptr); \ + typeof(*__vptr) __v; \ + type *__ptr = (void *) (_ptr); \ + unsigned long __start = (_start), __length = (_length); \ + type mask, cmask; \ + unsigned long ts = sizeof(type) * CHAR_BIT; /* type size */ \ + unsigned long start_unit, end_unit, this_unit; \ + unsigned long end, cshift; /* cshift is "complement shift" */ \ + \ + if (!__length) { \ + *__vptr = 0; \ + break; \ + } \ + \ + end = __start + __length; \ + start_unit = __start / ts; \ + end_unit = (end + (ts - 1)) / ts; \ + \ + this_unit = start_unit; \ + if (_ja_is_signed_type(typeof(__v)) \ + && (__ptr[this_unit] & ((type) 1 << (ts - (__start % ts) - 1)))) \ + __v = ~(typeof(__v)) 0; \ + else \ + __v = 0; \ + if (start_unit == end_unit - 1) { \ + cmask = __ptr[this_unit]; \ + cmask >>= (ts - (end % ts)) % ts; \ + if ((end - __start) % ts) { \ + mask = ~((~(type) 0) << (end - __start)); \ + cmask &= mask; \ + } \ + __v = _ja_piecewise_lshift(__v, end - __start); \ + __v |= _ja_unsigned_cast(typeof(__v), cmask); \ + *__vptr = __v; \ + break; \ + } \ + if (__start % ts) { \ + cshift = __start % ts; \ + mask = ~((~(type) 0) << (ts - cshift)); \ + cmask = __ptr[this_unit]; \ + cmask &= mask; \ + __v = _ja_piecewise_lshift(__v, ts - cshift); \ + __v |= _ja_unsigned_cast(typeof(__v), cmask); \ + __start += ts - cshift; \ + this_unit++; \ + } \ + for (; this_unit < end_unit - 1; this_unit++) { \ + __v = _ja_piecewise_lshift(__v, ts); \ + __v |= _ja_unsigned_cast(typeof(__v), __ptr[this_unit]);\ + __start += ts; \ + } \ + if (end % ts) { \ + mask = ~((~(type) 0) << (end % ts)); \ + cmask = __ptr[this_unit]; \ + cmask >>= ts - (end % ts); \ + cmask &= mask; \ + __v = _ja_piecewise_lshift(__v, end % ts); \ + __v |= _ja_unsigned_cast(typeof(__v), cmask); \ + } else { \ + __v = _ja_piecewise_lshift(__v, ts); \ + __v |= _ja_unsigned_cast(typeof(__v), __ptr[this_unit]);\ + } \ + *__vptr = __v; \ +} while (0) + +/* + * ja_bitfield_read - read integer from a bitfield in native endianness + * ja_bitfield_read_le - read integer from a bitfield in little endian + * ja_bitfield_read_be - read integer from a bitfield in big endian + */ + +#if (BYTE_ORDER == LITTLE_ENDIAN) + +#define ja_bitfield_read(_ptr, type, _start, _length, _vptr) \ + _ja_bitfield_read_le(_ptr, type, _start, _length, _vptr) + +#define ja_bitfield_read_le(_ptr, type, _start, _length, _vptr) \ + _ja_bitfield_read_le(_ptr, type, _start, _length, _vptr) + +#define ja_bitfield_read_be(_ptr, type, _start, _length, _vptr) \ + _ja_bitfield_read_be(_ptr, unsigned char, _start, _length, _vptr) + +#elif (BYTE_ORDER == BIG_ENDIAN) + +#define ja_bitfield_read(_ptr, type, _start, _length, _vptr) \ + _ja_bitfield_read_be(_ptr, type, _start, _length, _vptr) + +#define ja_bitfield_read_le(_ptr, type, _start, _length, _vptr) \ + _ja_bitfield_read_le(_ptr, unsigned char, _start, _length, _vptr) + +#define ja_bitfield_read_be(_ptr, type, _start, _length, _vptr) \ + _ja_bitfield_read_be(_ptr, type, _start, _length, _vptr) + +#else /* (BYTE_ORDER == PDP_ENDIAN) */ + +#error "Byte order not supported" + +#endif + +#endif /* _URCU_RCUJA_BITFIELD_H */ diff --git a/rcuja/endian.h b/rcuja/endian.h new file mode 100644 index 0000000..bf25a13 --- /dev/null +++ b/rcuja/endian.h @@ -0,0 +1,34 @@ +#ifndef _URCU_RCUJA_ENDIAN_H +#define _URCU_RCUJA_ENDIAN_H + +/* + * Copyright 2012 (c) - Mathieu Desnoyers + * + * endian.h compatibility layer. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + */ + +#ifdef __FreeBSD__ +#include +#else +#include +#endif + +#ifndef FLOAT_WORD_ORDER +#ifdef __FLOAT_WORD_ORDER +#define FLOAT_WORD_ORDER __FLOAT_WORD_ORDER +#else /* __FLOAT_WORD_ORDER */ +#define FLOAT_WORD_ORDER BYTE_ORDER +#endif /* __FLOAT_WORD_ORDER */ +#endif /* FLOAT_WORD_ORDER */ + +#endif /* _URCU_RCUJA_ENDIAN_H */ diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 012b874..8d3bfd7 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -21,10 +21,15 @@ */ #include +#include #include +#include +#include +#include #include "rcuja-internal.h" +#include "bitfield.h" -enum rcu_ja_child_type { +enum rcu_ja_type_class { RCU_JA_LINEAR = 0, /* Type A */ /* 32-bit: 1 to 12 children, 8 to 64 bytes */ /* 64-bit: 1 to 14 children, 16 to 128 bytes */ @@ -37,42 +42,67 @@ enum rcu_ja_child_type { /* Leaf nodes are implicit from their height in the tree */ }; -struct rcu_ja_type_select { - enum rcu_ja_child_type type; - uint16_t max_nr_child; /* 1 to 256 */ - uint16_t node_order; /* node size is (1 << node_order), in bytes */ +struct rcu_ja_type { + enum rcu_ja_type_class type_class; + uint16_t min_child; /* minimum number of children: 1 to 256 */ + uint16_t max_child; /* maximum number of children: 1 to 256 */ + uint16_t order; /* node size is (1 << order), in bytes */ }; +/* + * Number of least significant pointer bits reserved to represent the + * child type. + */ +#define JA_TYPE_BITS 3 +#define JA_TYPE_MAX_NR (1U << JA_TYPE_BITS) +#define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1) +#define JA_PTR_MASK (~JA_TYPE_MASK) + +#define JA_ENTRY_PER_NODE 256UL + /* * Iteration on the array to find the right node size for the number of - * children stops when it reaches max_nr_child == 0 (this is the largest + * children stops when it reaches .max_child == 256 (this is the largest * possible node size, which contains 256 children). + * The min_child overlaps with the previous max_child to provide an + * hysteresis loop to reallocation for patterns of cyclic add/removal + * within the same node. + * The node the index within the following arrays is represented on 3 + * bits. It identifies the node type, min/max number of children, and + * the size order. */ -const struct rcu_ja_type_select ja_select_u32[] = { - { .type = RCU_JA_LINEAR, .max_nr_child = 1, .node_order = 3, }, - { .type = RCU_JA_LINEAR, .max_nr_child = 3, .node_order = 4, }, - { .type = RCU_JA_LINEAR, .max_nr_child = 6, .node_order = 5, }, - { .type = RCU_JA_LINEAR, .max_nr_child = 12, .node_order = 6, }, - { .type = RCU_JA_BITMAP, .max_nr_child = 24, .node_order = 7, }, - { .type = RCU_JA_BITMAP, .max_nr_child = 56, .node_order = 8, }, - { .type = RCU_JA_BITMAP, .max_nr_child = 120, .node_order = 9, }, +#if (CAA_BITS_PER_LONG < 64) +/* 32-bit pointers */ +const struct rcu_ja_type ja_types[] = { + { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 1, .order = 3, }, + { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 3, .order = 4, }, + { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = 6, .order = 5, }, + { .type_class = RCU_JA_LINEAR, .min_child = 4, .max_child = 12, .order = 6, }, - { .type = RCU_JA_PIGEON, .max_nr_child = 256, .node_order = 10, }, -}; + { .type_class = RCU_JA_BITMAP, .min_child = 10, .max_child = 24, .order = 7, }, + { .type_class = RCU_JA_BITMAP, .min_child = 20, .max_child = 56, .order = 8, }, + { .type_class = RCU_JA_BITMAP, .min_child = 46, .max_child = 120, .order = 9, }, -const struct rcu_ja_type_select ja_select_u64[] = { - { .type = RCU_JA_LINEAR, .max_nr_child = 1, .node_order = 4, }, - { .type = RCU_JA_LINEAR, .max_nr_child = 3, .node_order = 5, }, - { .type = RCU_JA_LINEAR, .max_nr_child = 7, .node_order = 6, }, - { .type = RCU_JA_LINEAR, .max_nr_child = 14, .node_order = 7, }, + { .type_class = RCU_JA_PIGEON, .min_child = 100, .max_child = 256, .order = 10, }, +}; +CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR); +#else /* !(CAA_BITS_PER_LONG < 64) */ +/* 64-bit pointers */ +const struct rcu_ja_type ja_types[] = { + { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 1, .order = 4, }, + { .type_class = RCU_JA_LINEAR, .min_child = 1, .max_child = 3, .order = 5, }, + { .type_class = RCU_JA_LINEAR, .min_child = 3, .max_child = 7, .order = 6, }, + { .type_class = RCU_JA_LINEAR, .min_child = 5, .max_child = 14, .order = 7, }, - { .type = RCU_JA_BITMAP, .max_nr_child = 28, .node_order = 8, }, - { .type = RCU_JA_BITMAP, .max_nr_child = 60, .node_order = 9, }, - { .type = RCU_JA_BITMAP, .max_nr_child = 124, .node_order = 10, }, + { .type_class = RCU_JA_BITMAP, .min_child = 10, .max_child = 28, .order = 8, }, + { .type_class = RCU_JA_BITMAP, .min_child = 22, .max_child = 60, .order = 9, }, + { .type_class = RCU_JA_BITMAP, .min_child = 49, .max_child = 124, .order = 10, }, - { .type = RCU_JA_PIGEON, .max_nr_child = 256, .node_order = 11, }, + { .type_class = RCU_JA_PIGEON, .min_child = 102, .max_child = 256, .order = 11, }, }; +CAA_BUILD_BUG_ON(CAA_ARRAY_SIZE(ja_types) > JA_TYPE_MAX_NR); +#endif /* !(BITS_PER_LONG < 64) */ /* * The rcu_ja_node starts with a byte counting the number of children in @@ -85,9 +115,35 @@ struct rcu_ja_node { char data[]; }; -struct rcu_ja_node *create_rcu_ja_node(struct rcu_ja_type_select *sel) +/* Never declared. Opaque type used to store flagged node pointers. */ +struct rcu_ja_node_flag; + +static +struct rcu_ja_node_flag *ja_node_flag(struct rcu_ja_node *node, unsigned int type) +{ + assert(type < JA_TYPE_NR); + return (struct rcu_ja_node_flag *) (((unsigned long) node) | type); +} + +static +unsigned int ja_node_type(struct rcu_ja_node_flag *node) +{ + unsigned int type; + + type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK); + assert(type < JA_TYPE_NR); + return type; +} + +static +struct rcu_ja_node *ja_node_ptr(struct rcu_ja_node_flag *node) +{ + return (struct rcu_ja_node *) (((unsigned long) node) | JA_PTR_MASK); +} + +struct rcu_ja_node *alloc_rcu_ja_node(struct rcu_ja_type *ja_type) { - return zmalloc(1 << sel->node_order); + return zmalloc(1 << ja_type->node_order); } void free_rcu_ja_node(struct rcu_ja_node *node) @@ -95,5 +151,211 @@ void free_rcu_ja_node(struct rcu_ja_node *node) free(node); } +/* The bitmap for 256 entries is always 32 bytes */ +#define CHAR_BIT_SHIFT 3UL +#define CHAR_BIT_MASK ((1UL << CHAR_BIT_SHIFT) - 1) +#if (CHAR_BIT != (1UL << CHAR_BIT_SHIFT)) +#error "char size not supported." +#endif + +#define ULONG_BIT_MASK (CAA_BITS_PER_LONG - 1) + +#define JA_BITMAP_BITS JA_ENTRY_PER_NODE +#define JA_BITMAP_LEN (JA_BITMAP_BITS / CHAR_BIT) + +#define __JA_ALIGN_MASK(v, mask) (((v) + (mask)) & ~(mask)) +#define JA_ALIGN(v, align) __JA_ALIGN_MASK(v, (typeof(v)) (align) - 1) +#define __JA_FLOOR_MASK(v, mask) ((v) & ~(mask)) +#define JA_FLOOR(v, align) __JA_FLOOR_MASK(v, (typeof(v)) (align) - 1) + +static +char *align_ptr_size(char *ptr) +{ + return JA_ALIGN(ptr, sizeof(ptr)); +} + +static +struct rcu_ja_node_flag *ja_linear_node_get_nth(const struct rcu_ja_type *type, + struct rcu_ja_node *node, + uint8_t n) +{ + uint8_t nr_child; + uint8_t *values; + struct rcu_ja_node_flag *pointers; + struct rcu_ja_node_flag *ptr; + unsigned int i; + + assert(type->type_class == RCU_JA_LINEAR); + + nr_child = node->data[0]; + cmm_smp_rmb(); /* read nr_child before values */ + assert(nr_child <= type->max_child); + assert(nr_child >= type->min_child); + + values = &node[1]; + for (i = 0; i < nr_child; i++) { + if (values[i] == n) + break; + } + if (i >= nr_child) + return NULL; + cmm_smp_rmb(); /* read values before pointer */ + pointers = align_ptr_size(&values[nr_child]); + ptr = pointers[i]; + assert(ja_node_ptr(ptr) != NULL); + return ptr; +} + +#if 0 +/* + * Count hweight. Expect most bits to be 0. Algorithm from + * Wegner (1960): count those in n steps (n being the number of + * hot bits). Ref.: Wegner, Peter (1960), "A technique for + * counting ones in a binary computer", Communications of the + * ACM 3 (5): 322, doi:10.1145/367236.367286. + */ +static +unsigned int ja_hweight_uchar(unsigned char value) +{ + unsigned int count = 0; + + for (; value; count++) + value &= value - 1; + return count; +} +#endif //0 + +#if (CAA_BITS_PER_LONG < 64) +static +unsigned int ja_hweight_ulong(unsigned long value) +{ + unsigned long r; + + r = value; + r = r - ((r >> 1) & 0x55555555); + r = (r & 0x33333333) + ((r >> 2) & 0x33333333); + r += r >> 4; + r &= 0x0F0F0F0F; + r += r >> 8; + r += r >> 16; + r &= 0x000000FF; + return r; +} +#else /* !(CAA_BITS_PER_LONG < 64) */ +static +unsigned int ja_hweight_ulong(unsigned long value) +{ + unsigned long r; + + r = value; + r = r - ((r >> 1) & 0x5555555555555555UL); + r = (r & 0x3333333333333333UL) + ((r >> 2) & 0x3333333333333333UL); + r += r >> 4; + r &= 0x0F0F0F0F0F0F0F0FUL; + r += r >> 8; + r += r >> 16; + r += r >> 32; + r &= 0x00000000000000FFUL; + return r; +} +#endif /* !(BITS_PER_LONG < 64) */ + +static +struct rcu_ja_node_flag *ja_bitmap_node_get_nth(const struct rcu_ja_type *type, + struct rcu_ja_node *node, + uint8_t n) +{ + uint8_t *bitmap; + uint8_t byte_nr; + struct rcu_ja_node_flag *pointers; + struct rcu_ja_node_flag *ptr; + unsigned int count; + + assert(type->type_class == RCU_JA_BITMAP); + bitmap = &node->data[0]; + /* + * Check if n is hot in the bitmap. If yes, count the hweight + * prior to n, including n, to get the pointer index. + * The bitmap goes from least significant (0) to most + * significant (255) as bytes increase. + */ + byte_nr = n >> CHAR_BIT_SHIFT; + if (bitmap[byte_nr] & (1U << (n & CHAR_BIT_MASK))) { + uint8_t byte_iter; + unsigned long v; + + count = 0; + /* Count entire ulong prior to the one containing n */ + for (byte_iter = 0; byte_iter < JA_FLOOR(byte_nr, sizeof(unsigned long)); + byte_iter += sizeof(unsigned long)) { + v = *((unsigned long *) &bitmap[byte_iter]); + count += ja_hweight_ulong(v); + } + /* + * Read only the bits prior to and including n within + * the ulong containing n. ja_bitfield_read_le goes from + * less significant to most significant as bytes + * increase. + */ + ja_bitfield_read_le( + (unsigned long *) &bitmap[JA_FLOOR(byte_nr, sizeof(unsigned long))], + unsigned long, 0, (n & ULONG_BIT_MASK) + 1, + &v); + count += ja_hweight_ulong(v); + } else { + return NULL; + } + + assert(count <= type->max_child); + assert(count >= type->min_child); + + cmm_smp_rmb(); /* read bitmap before pointers */ + pointers = &bitmap[JA_BITMAP_LEN]; + ptr = pointers[count - 1]; + assert(ja_node_ptr(ptr) != NULL); + return ptr; +} + +static +struct rcu_ja_node_flag *ja_pigeon_node_get_nth(const struct rcu_ja_type *type, + struct rcu_ja_node *node, + uint8_t n) +{ + assert(type->type_class == RCU_JA_PIGEON); + return ((struct rcu_ja_node_flag *) node->data)[n]; +} + +/* ja_node_get_nth: get nth item from a node */ +static +struct rcu_ja_node_flag *ja_node_get_nth(struct rcu_ja_node_flag *node_flag, + uint8_t n) +{ + unsigned int type_index; + struct rcu_ja_node *node; + const struct rcu_ja_type *type; + + node_flag = rcu_dereference(node_flag); + node = ja_node_ptr(node_flag); + assert(node != NULL); + type_index = ja_node_type(node_flag); + type = &ja_types[type_index]; + + switch (type->type_class) { + case RCU_JA_LINEAR: + return ja_linear_node_get_nth(type, node, n); + case RCU_JA_BITMAP: + return ja_bitmap_node_get_nth(type, node, n); + case RCU_JA_PIGEON: + return ja_pigeon_node_get_nth(type, node, n); + default: + assert(0); + return (void *) -1UL; + } +} + +/* + * ja_node_set_nth: set nth item within a node. asserts that it is not + * there yet. + */ diff --git a/urcu/compiler.h b/urcu/compiler.h index 318ca65..c4ade90 100644 --- a/urcu/compiler.h +++ b/urcu/compiler.h @@ -101,4 +101,6 @@ __attribute__((deprecated)) #endif +#define CAA_ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + #endif /* _URCU_COMPILER_H */ -- 2.34.1