Re: [PATCH v6 0/25] Generic Red-Black Trees
On 10/01/2012 03:47 PM, Andrew Morton wrote: > On Mon, 01 Oct 2012 15:41:14 -0500 > Daniel Santos wrote: > >> I can rebase against whatever you like and send either corrections or an >> updated patch set. Just tell me what works please. > I dropped everything - let's start again. I would have sent you my updated patch set, but both -mmotm and -next are broken on my hardware at the moment and I can't properly re-test. I posted a bug here: https://bugzilla.kernel.org/show_bug.cgi?id=48241 (with early boot jpg). I can rebase it against Linus maybe for testing (just a few changes). I did use gcc 4.7.1, so I'm going to try using gcc 4.6.3 just to make sure it's not that. But it looks like I may have a few more changes to make anyway. Daniel -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
On 10/01/2012 03:47 PM, Andrew Morton wrote: On Mon, 01 Oct 2012 15:41:14 -0500 Daniel Santos danielfsan...@att.net wrote: I can rebase against whatever you like and send either corrections or an updated patch set. Just tell me what works please. I dropped everything - let's start again. I would have sent you my updated patch set, but both -mmotm and -next are broken on my hardware at the moment and I can't properly re-test. I posted a bug here: https://bugzilla.kernel.org/show_bug.cgi?id=48241 (with early boot jpg). I can rebase it against Linus maybe for testing (just a few changes). I did use gcc 4.7.1, so I'm going to try using gcc 4.6.3 just to make sure it's not that. But it looks like I may have a few more changes to make anyway. Daniel -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
Andrew,
I'm really sorry for the debacle of this round of patches. It turns out
that my patches weren't reaching LKML because my recipient list was too
large
and the server was tagging it as spam, so none of these patches you
committed
ever made it to LKML. :( To fix that, I broke the 25 patches
into 3 smaller sets.
[PATCH 0/10] Cleanup & new features for compiler*.h and bug.h
[PATCH 0/3] kernel-doc bug fixes
[PATCH v6 0/10] Generic Red-Black Trees
On 10/01/2012 02:43 PM, Andrew Morton wrote:
> On Thu, 27 Sep 2012 20:54:16 -0500
> Daniel Santos wrote:
>
>> This patch set improves on Andrea Arcangeli's original Red-Black Tree
>> implementation by adding generic search and insert functions with
>> complete support for:
>
> I grabbed patches 1-7, but I don't expect to send them in for 3.7.
> It's not a good time to be merging new material, but I like cleanups.
>
I probably should have bumped the version to 7 to reduce the confusion.
Some maintainers have requested some changes in some of the first 10
patches (the compiler*.h & bug.h). Can you roll them back or is it
better to
just send the corrections?
So one change, which you noted ("[PATCH v6 4/25] compiler-gcc{3,4}.h: Use
GCC_VERSION macro" is now "[PATCH 4/10]..." of the "Cleanup & new
features for
compiler*.h and bug.h" patch set.
>> /* GCC 4.1.[01] miscompiles __weak */
>> #ifdef __KERNEL__
>> -# if __GNUC_MINOR__ == 1 && __GNUC_PATCHLEVEL__ <= 1
>> +# if GCC_VERSION >= 40100 && GCC_VERSION <= 40101
>> //# error Your version of gcc miscompiles the __weak directive
>> # endif
>> #endif
>> @@ -13,11 +13,11 @@
>> #define __must_check__attribute__((warn_unused_result))
>> #define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
>>
>> -#if __GNUC_MINOR__ > 0
>> +#if GCC_VERSION >= 40102
> Is this correct (and clear)? I'd expect
>
> #if GCC_VERSION > 4
This should actually be gcc 4.1.0 or higher. I was going from the
presumption
that 4.1.0 & 4.1.1 wouldn't compile due to the __weak thing above, but
that's
unrelated (and now commented out), so it should just be >= 4.1.0.
#if GCC_VERSION >= 40100
They also want the order of patches 5 & 6 reversed (breaks build in between
otherwise) and patch notes added to the patch "[PATCH 6/10] bug.h: Replace
__linktime_error with __compiletime_error" and we're going to rework
BUILD_BUG_ON.
I can rebase against whatever you like and send either corrections or an
updated patch set. Just tell me what works please.
Thank you for your patience as I learn the ropes in this project.
Daniel
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
On Mon, 01 Oct 2012 15:41:14 -0500 Daniel Santos wrote: > I can rebase against whatever you like and send either corrections or an > updated patch set. Just tell me what works please. I dropped everything - let's start again. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
On Thu, 27 Sep 2012 20:54:16 -0500 Daniel Santos wrote: > This patch set improves on Andrea Arcangeli's original Red-Black Tree > implementation by adding generic search and insert functions with > complete support for: I grabbed patches 1-7, but I don't expect to send them in for 3.7. It's not a good time to be merging new material, but I like cleanups. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
On Thu, 27 Sep 2012 20:54:16 -0500 Daniel Santos daniel.san...@pobox.com wrote: This patch set improves on Andrea Arcangeli's original Red-Black Tree implementation by adding generic search and insert functions with complete support for: I grabbed patches 1-7, but I don't expect to send them in for 3.7. It's not a good time to be merging new material, but I like cleanups. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
On Mon, 01 Oct 2012 15:41:14 -0500 Daniel Santos danielfsan...@att.net wrote: I can rebase against whatever you like and send either corrections or an updated patch set. Just tell me what works please. I dropped everything - let's start again. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v6 0/25] Generic Red-Black Trees
Andrew,
I'm really sorry for the debacle of this round of patches. It turns out
that my patches weren't reaching LKML because my recipient list was too
large
and the server was tagging it as spam, so none of these patches you
committed
ever made it to LKML. :( To fix that, I broke the 25 patches
into 3 smaller sets.
[PATCH 0/10] Cleanup new features for compiler*.h and bug.h
[PATCH 0/3] kernel-doc bug fixes
[PATCH v6 0/10] Generic Red-Black Trees
On 10/01/2012 02:43 PM, Andrew Morton wrote:
On Thu, 27 Sep 2012 20:54:16 -0500
Daniel Santos daniel.san...@pobox.com wrote:
This patch set improves on Andrea Arcangeli's original Red-Black Tree
implementation by adding generic search and insert functions with
complete support for:
I grabbed patches 1-7, but I don't expect to send them in for 3.7.
It's not a good time to be merging new material, but I like cleanups.
I probably should have bumped the version to 7 to reduce the confusion.
Some maintainers have requested some changes in some of the first 10
patches (the compiler*.h bug.h). Can you roll them back or is it
better to
just send the corrections?
So one change, which you noted ([PATCH v6 4/25] compiler-gcc{3,4}.h: Use
GCC_VERSION macro is now [PATCH 4/10]... of the Cleanup new
features for
compiler*.h and bug.h patch set.
/* GCC 4.1.[01] miscompiles __weak */
#ifdef __KERNEL__
-# if __GNUC_MINOR__ == 1 __GNUC_PATCHLEVEL__ = 1
+# if GCC_VERSION = 40100 GCC_VERSION = 40101
//# error Your version of gcc miscompiles the __weak directive
# endif
#endif
@@ -13,11 +13,11 @@
#define __must_check__attribute__((warn_unused_result))
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
-#if __GNUC_MINOR__ 0
+#if GCC_VERSION = 40102
Is this correct (and clear)? I'd expect
#if GCC_VERSION 4
This should actually be gcc 4.1.0 or higher. I was going from the
presumption
that 4.1.0 4.1.1 wouldn't compile due to the __weak thing above, but
that's
unrelated (and now commented out), so it should just be = 4.1.0.
#if GCC_VERSION = 40100
They also want the order of patches 5 6 reversed (breaks build in between
otherwise) and patch notes added to the patch [PATCH 6/10] bug.h: Replace
__linktime_error with __compiletime_error and we're going to rework
BUILD_BUG_ON.
I can rebase against whatever you like and send either corrections or an
updated patch set. Just tell me what works please.
Thank you for your patience as I learn the ropes in this project.
Daniel
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH v6 0/25] Generic Red-Black Trees
This revised patch set is rebased onto linux-mmotm.
I have a new mail provider now, but they seem just as bad as the last, so I'm
going to try to split the recpients in half and pray that this goes through.
I'm sorry to those of you who have gotten partial patch sets and I hope to get
this fixed soon. (If anybody knows of a descent email service for developers
who send patches, please let me know.)
Summary
===
This patch set improves on Andrea Arcangeli's original Red-Black Tree
implementation by adding generic search and insert functions with
complete support for:
o leftmost - keeps a pointer to the leftmost (lowest value) node cached
in your container struct
o rightmost - ditto for rightmost (greatest value)
o count - optionally update an count variable when you perform inserts
or deletes
o unique or non-unique keys
o find and insert "near" functions - when you already have a node that
is likely near another one you want to search for
o type-safe wrapper interface available via pre-processor macro
Outstanding Issues
==
General
---
o Need something in Documents to explain generic rbtrees.
o Due to a bug in gcc's optimizer, extra instructions are generated in various
places. Pavel Pisa has provided me a possible work-around that should be
examined more closely to see if it can be working in (Discussed in
Performance section).
o Doc-comments are missing or out of date in some places for the new
ins_compare field of struct rb_relationship (including at least one code
example).
Selftests
-
o In-kernel test module not completed.
o Userspace selftest's Makefile should run modules_prepare in KERNELDIR.
o Validation in self-tests doesn't yet cover tests for
- insert_near
- find_{first,last,next,prev}
o Selftest scripts need better portability (maybe solved? we'll see)
o It would be nice to have some fault-injection in test code to verify that
CONFIG_DEBUG_GRBTREE and CONFIG_DEBUG_GRBTREE_VALIDATE (and it's
RB_VERIFY_INTEGRITY counterpart flag) catch the errors they are supposed to.
Undecided (Opinions Requested!)
---
o With the exception of the rb_node & rb_root structs, "Layer 2" of the code
(see below) completely abstracts away the underlying red-black tree
mechanism. The structs rb_node and rb_root can also be abstracted away via
a typeset or some other mechanism. Thus, should the "Layer 2" code be
separated from "Layer 1" and renamed "Generic Tree (gtree)" or some such,
paving the way for an alternate tree implementation in the future?
o Do we need RB_INSERT_DUPE_RIGHT? (see the last patch)
Theory of Operation
===
Historically, genericity in C meant function pointers, the overhead of a
function call and the inability of the compiler to optimize code across
the function call boundary. GCC has been getting better and better at
optimization and determining when a value is a compile-time constant and
compiling it out. As of gcc 4.6, it has finally reached a point where
it's possible to have generic search & insert cores that optimize
exactly as well as if they were hand-coded. (see also gcc man page:
-findirect-inlining)
This implementation actually consists of two layers written on top of the
existing rbtree implementation.
Layer 1: Type-Specific (But Not Type-Safe)
--
The first layer consists of enum rb_flags, struct rb_relationship and
some generic inline functions(see patch for doc comments).
enum rb_flags {
RB_HAS_LEFTMOST = 0x0001,
RB_HAS_RIGHTMOST= 0x0002,
RB_HAS_COUNT= 0x0004,
RB_UNIQUE_KEYS = 0x0008,
RB_INSERT_REPLACES = 0x0010,
RB_IS_AUGMENTED = 0x0040,
RB_VERIFY_USAGE = 0x0080,
RB_VERIFY_INTEGRITY = 0x0100
};
struct rb_relationship {
ssize_t root_offset;
ssize_t left_offset;
ssize_t right_offset;
ssize_t count_offset;
ssize_t node_offset;
ssize_t key_offset;
int flags;
const rb_compare_f compare; /* comparitor for lookups */
const rb_compare_f ins_compare; /* comparitor for inserts */
unsigned key_size;
};
/* these function for use on all trees */
struct rb_node *rb_find(
struct rb_root *root,
const void *key,
const struct rb_relationship *rel);
struct rb_node *rb_find_near(
struct rb_node *from,
const void *key,
const struct rb_relationship *rel);
struct rb_node *rb_insert(
struct rb_root *root,
struct rb_node *node,
const struct rb_relationship *rel);
struct rb_node *rb_insert_near(
struct rb_root *root,
struct rb_node *start,
struct rb_node *node,
const struct rb_relationship *rel);
void
[PATCH v6 0/25] Generic Red-Black Trees
This revised patch set is rebased onto linux-mmotm.
I have a new mail provider now, but they seem just as bad as the last, so I'm
going to try to split the recpients in half and pray that this goes through.
I'm sorry to those of you who have gotten partial patch sets and I hope to get
this fixed soon. (If anybody knows of a descent email service for developers
who send patches, please let me know.)
Summary
===
This patch set improves on Andrea Arcangeli's original Red-Black Tree
implementation by adding generic search and insert functions with
complete support for:
o leftmost - keeps a pointer to the leftmost (lowest value) node cached
in your container struct
o rightmost - ditto for rightmost (greatest value)
o count - optionally update an count variable when you perform inserts
or deletes
o unique or non-unique keys
o find and insert near functions - when you already have a node that
is likely near another one you want to search for
o type-safe wrapper interface available via pre-processor macro
Outstanding Issues
==
General
---
o Need something in Documents to explain generic rbtrees.
o Due to a bug in gcc's optimizer, extra instructions are generated in various
places. Pavel Pisa has provided me a possible work-around that should be
examined more closely to see if it can be working in (Discussed in
Performance section).
o Doc-comments are missing or out of date in some places for the new
ins_compare field of struct rb_relationship (including at least one code
example).
Selftests
-
o In-kernel test module not completed.
o Userspace selftest's Makefile should run modules_prepare in KERNELDIR.
o Validation in self-tests doesn't yet cover tests for
- insert_near
- find_{first,last,next,prev}
o Selftest scripts need better portability (maybe solved? we'll see)
o It would be nice to have some fault-injection in test code to verify that
CONFIG_DEBUG_GRBTREE and CONFIG_DEBUG_GRBTREE_VALIDATE (and it's
RB_VERIFY_INTEGRITY counterpart flag) catch the errors they are supposed to.
Undecided (Opinions Requested!)
---
o With the exception of the rb_node rb_root structs, Layer 2 of the code
(see below) completely abstracts away the underlying red-black tree
mechanism. The structs rb_node and rb_root can also be abstracted away via
a typeset or some other mechanism. Thus, should the Layer 2 code be
separated from Layer 1 and renamed Generic Tree (gtree) or some such,
paving the way for an alternate tree implementation in the future?
o Do we need RB_INSERT_DUPE_RIGHT? (see the last patch)
Theory of Operation
===
Historically, genericity in C meant function pointers, the overhead of a
function call and the inability of the compiler to optimize code across
the function call boundary. GCC has been getting better and better at
optimization and determining when a value is a compile-time constant and
compiling it out. As of gcc 4.6, it has finally reached a point where
it's possible to have generic search insert cores that optimize
exactly as well as if they were hand-coded. (see also gcc man page:
-findirect-inlining)
This implementation actually consists of two layers written on top of the
existing rbtree implementation.
Layer 1: Type-Specific (But Not Type-Safe)
--
The first layer consists of enum rb_flags, struct rb_relationship and
some generic inline functions(see patch for doc comments).
enum rb_flags {
RB_HAS_LEFTMOST = 0x0001,
RB_HAS_RIGHTMOST= 0x0002,
RB_HAS_COUNT= 0x0004,
RB_UNIQUE_KEYS = 0x0008,
RB_INSERT_REPLACES = 0x0010,
RB_IS_AUGMENTED = 0x0040,
RB_VERIFY_USAGE = 0x0080,
RB_VERIFY_INTEGRITY = 0x0100
};
struct rb_relationship {
ssize_t root_offset;
ssize_t left_offset;
ssize_t right_offset;
ssize_t count_offset;
ssize_t node_offset;
ssize_t key_offset;
int flags;
const rb_compare_f compare; /* comparitor for lookups */
const rb_compare_f ins_compare; /* comparitor for inserts */
unsigned key_size;
};
/* these function for use on all trees */
struct rb_node *rb_find(
struct rb_root *root,
const void *key,
const struct rb_relationship *rel);
struct rb_node *rb_find_near(
struct rb_node *from,
const void *key,
const struct rb_relationship *rel);
struct rb_node *rb_insert(
struct rb_root *root,
struct rb_node *node,
const struct rb_relationship *rel);
struct rb_node *rb_insert_near(
struct rb_root *root,
struct rb_node *start,
struct rb_node *node,
const struct rb_relationship *rel);
void rb_remove(
