linux-kernel - Re: [PATCH v4 0/13] Generic Red-Black Trees

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]

Message-Id: <201206240957.09136.pisa@cmp.felk.cvut.cz>
Date:	Sun, 24 Jun 2012 09:57:08 +0200
From:	Pavel Pisa <pisa@....felk.cvut.cz>
To:	Rob Landley <rob@...dley.net>
Cc:	daniel.santos@...ox.com, Daniel Santos <danielfsantos@....net>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Christopher Li <sparse@...isli.org>,
	David Daney <david.daney@...ium.com>,
	David Howells <dhowells@...hat.com>,
	David Rientjes <rientjes@...gle.com>,
	Hidetoshi Seto <seto.hidetoshi@...fujitsu.com>,
	"H. Peter Anvin" <hpa@...or.com>, Ingo Molnar <mingo@...e.hu>,
	Ingo Molnar <mingo@...nel.org>, Joe Perches <joe@...ches.com>,
	Konstantin Khlebnikov <khlebnikov@...nvz.org>,
	linux-doc@...r.kernel.org, linux-sparse@...r.kernel.org,
	LKML <linux-kernel@...r.kernel.org>,
	Paul Gortmaker <paul.gortmaker@...driver.com>,
	Paul Turner <pjt@...gle.com>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Richard Weinberger <richard@....at>,
	Steven Rostedt <rostedt@...dmis.org>,
	Suresh Siddha <suresh.b.siddha@...el.com>
Subject: Re: [PATCH v4 0/13] Generic Red-Black Trees

Hello Rob,

I follow-up Daniel's RB series from Jonathan Corbet's
summarry on LWN http://lwn.net/Articles/500355/ .

I have attempted ourself to solve implementation of
type safe tree containers for C more than 10 years ago
(GAVL) and it is used in many of my own and our university
projects and even in (at least three) companies for
proprietary projects.

I have done multiple reviews of the Daniel's RB series
and I am confident that his approach is more clean
and generic than mine.

I would be happy if it can get into Linux kernel,
because it makes use of RB trees much simpler (user does
not need to care about details) and with much better
potential to catch user errors.

According to my review, there is only one possibly problematic
preprocessor construct. The Linux kernel is already dependent
on this CPP behavior (IS_ENABLED macro) anyway.

If you are fan of other compilers, please, provide
constructive help and debate there and test attached
C code on compilers which you use and consider
them as candidates to compile linux kernel.

According to my test, there is problem with MSVC
(free WDF version run under WINE to deliver our company
open-source projects to unfortunate users using Windows).

Version

Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.207 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.

But that is compiler which breaks many standards
and if GCC is not enough open to you then I expect that
you do not mind if Linux kernel cannot be compiled by MSVC.
So I do not see that as a problem.

So again, please, test LLVM or other your beloved
compilers and report if there is a problem.

It would worth to have even user space version of the
kernel RB tree code with Dainie's interface to run feasibility
and performance tests in more environments quickly
(as Daniel mentioned already). But it is not necessary
for me to be convinced that provided changes should go into
kernel because I am convinced  already and offer my
"Reviewed-by" confirmation.

It would even worth to have this code available for
user space projects and libraries use. But there is a problem
that core part of the Linux RB code is GPL licensed
and for library use LGPL, MPL or GPL with linking exception
is usually required.

Best wishes,

                Pavel Pisa
    e-mail:     pisa@....felk.cvut.cz
    www:        http://cmp.felk.cvut.cz/~pisa
    university: http://dce.fel.cvut.cz/
    company:    http://www.pikron.com/

#include <stdio.h>

#define IFF_EMPTY(test, t, f) _iff_empty(__JUNK##test, t, f)

#define __JUNK junk ,
#define _iff_empty(test_or_junk, t, f) __iff_empty(test_or_junk, t, f)
#define __iff_empty(__ignored1, __ignored2, result, ...) result

#define IS_EMPTY(arg)	IFF_EMPTY(arg, 1, 0)

#define TESTER_empty
#define TESTER_filled filled

int main(int argc, char *argv[])
{
  printf("IS_EMPTY for empty %d (should be 1)\n", IS_EMPTY(TESTER_empty));
  printf("IS_EMPTY for filled %d (should be 0)\n", IS_EMPTY(TESTER_filled));
  printf("IS_EMPTY for unknown %d (should be 0)\n", IS_EMPTY(TESTER_unknown));
  printf("IS_EMPTY for nil %d (should be 1)\n", IS_EMPTY());
  printf("IS_EMPTY for space %d (should be 1)\n", IS_EMPTY( ));
  printf("IS_EMPTY for comment %d (should be 1)\n", IS_EMPTY(/*test*/));
}

--
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/