linux-kernel - Re: Generic Red-Black Trees (status update)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 25 May 2012 16:02:41 -0700
From:	Andi Kleen <andi@...stfloor.org>
To:	daniel.santos@...ox.com
Cc:	linux-kernel@...r.kernel.org
Subject: Re: Generic Red-Black Trees (status update)

Daniel Santos <danielfsantos@....net> writes:

> For anybody that's keeping up with this, I've gone through multiple
> iterations and tests with 9 different gcc versions and concluded that
> the search, insert & remove cores need to be coded in rbtree.h, using
> the traditional interface (i.e., passing struct rb_node & rb_root
> pointers instead of pointers to your specific object types).  The reason
> is that gcc can't handle the cool fully-generic code until 4.6.  In gcc
> 4.5.x, optimization completely breaks expanding the inline functions

Can you post details?

> into huge bloated  monsters.  Also, while I'm re-coding it all, I'm
> adding find_near & insert_near, for more efficient insertion & retrieval
> when you already have a node that should be close to the one you want
> (which is often the case when inserting many objects at once).
>
> So after I'm done with this, I'll start on a new header file (grbtree.h
> probably) using the "grb_" prefix for it's functions that implements the
> gcc 4.6.x+ fully generic & type safe interface, but using cute
> pre-processor tricks for pre-4.6.x compatibility (basically, something
> to consider using once gcc 4.6+ is more widely used).

That doesn't make sense. Either it's used or it's not used,
but if it's available it should work with all compilers.

Otherwise you would end up with drivers or subsystems that
are compiler specific.

It's ok to be somewhat slower or bigger on older compilers.



-Andi

-- 
ak@...ux.intel.com -- Speaking for myself only
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/