linux-kernel - Generic rbtree search & insert cores

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: Windows password security audit tool. GUI, reports in PDF.

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

Date:	Mon, 30 Apr 2012 06:11:33 -0500
From:	Daniel Santos <danielfsantos@....net>
To:	Andrea Arcangeli <aarcange@...hat.com>
CC:	linux-kernel@...r.kernel.org
Subject: Generic rbtree search & insert cores

I believe I've solved the problem of having generic search & insert cores in C.  Attached is my current working version of rbtree_ext.h.  While I've included an example in my documentation, here's a quickie:

/* Header File */
#include <linux/rbtree_ext.h>

struct house {
    struct rb_root mice;
};

struct mouse {
    struct rb_node node;
    const char*    name;
};

extern struct mouse *find_mouse(struct house *house, const char *name);
extern struct mouse *put_mouse_in_house(struct house *house,
                    struct mouse *mouse);

/* Implementation File */
#include "myheader.h"

static inline int name_cmp(const char **a, const char **b) {
    return strcmp(*a, *b);
}

static const struct rbtree_relationship rel_house_to_mouse = {
    .root_offset = offsetof(struct house, mice),
    .node_offset = offsetof(struct mouse, node),
    .key_offset  = offsetof(struct mouse, name),
    .compare     = (int(*)(const void*, const void*))name_cmp;
};

/* inline expansion occurs here and our object file doesn't bloat */
struct mouse *find_mouse(struct house *house, const char *name) {
    return rbtree_find(house, name, &rel_house_to_mouse);
}

struct mouse *put_mouse_in_house(struct house *house, struct mouse *mouse) {
    return rbtree_insert(house, mouse, 1, &rel_house_to_mouse);
}

So as long as our struct rbtree_relationship is a compile-time constant, the generated code will look pretty much (if not exactly) like that of the example code in rbtree.h.  Please let me know what you think.  I've tested this in a userspace program, but haven't fully stress tested it in kernelspace yet.

Daniel


View attachment "rbtree_ext.h" of type "text/x-chdr" (10180 bytes)