linux-kernel - Re: [PATCH 02/16] DRBD: lru

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:	Sat, 2 May 2009 21:39:54 +0200
From:	Lars Ellenberg <lars.ellenberg@...bit.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Philipp Reisner <philipp.reisner@...bit.com>,
	linux-kernel@...r.kernel.org, Jens Axboe <jens.axboe@...cle.com>,
	Greg KH <gregkh@...e.de>, Neil Brown <neilb@...e.de>,
	James Bottomley <James.Bottomley@...senPartnership.com>,
	Sam Ravnborg <sam@...nborg.org>, Dave Jones <davej@...hat.com>,
	Nikanth Karthikesan <knikanth@...e.de>,
	Lars Marowsky-Bree <lmb@...e.de>,
	"Nicholas A. Bellinger" <nab@...ux-iscsi.org>,
	Kyle Moffett <kyle@...fetthome.net>,
	Bart Van Assche <bart.vanassche@...il.com>
Subject: Re: [PATCH 02/16] DRBD: lru_cache

On Sat, May 02, 2009 at 11:26:09AM -0700, Andrew Morton wrote:
> You appear to believe that I understood the relevance of all the above
> text.  I didn't ;)
> 
> Let's start again.
> 
> Why can't I do
> 
> struct foo {
> 	int x;
> 	struct lc_element lc;
> 	..
> };
> 
> and then use the lru library code to handle my foo objects?


to do so, you'd
struct lru_cache *foo_cache =
	lc_alloc("dummy", 42, sizeof(struct foo), NULL);

that would alloc 
sizeof(struct lru_cache)
+ 42 * sizeof(struct hlist_head)
+ 42 * sizeof(struct foo);

the number of elements in the cache is fixed for its lifetime,
only the reference counts, position on the lru lists,
and tracked "house numbers" change.

the lru code sometimes addresses the lc_element part of the object
just via their index in this memory area, which is useful to initialize
the elements from some on-disk recorded state.

it does so by assuming a struct lc_element
every sizeof(struct foo) bytes
after the initial 42 hlist slots.

there, that was it.

to make this generic, appart from adding some paranoia
like a BUG_ON(sizeof(foo) < sizeof(lc_element)), and possibly
rounding any "odd" element_size parameter to get proper alignment,
it would need to pass in offset_of(struct foo, lc),
so it could do 

#define lc_e_base(lc) \
        ((char *)((lc)->slot + (lc)->nr_elements))

static inline struct lc_element *
lc_element_by_index(struct lru_cache *lc, unsigned int i)
{
        BUG_ON(i >= lc->nr_elements);
        return (struct lc_element *) (lc_e_base(lc)
			+ i * lc->element_size
			+     lc->offset_of);
}

lc->offset_of is what is currently missing from the code.
lc_element_by_index() is what currently is badly named lc_entry().

a real lc_entry would then become
#define lc_entry(ptr, type, member) \
        container_of(ptr, type, member)

so what now is
-struct foo *bar = (struct foo *) lc_entry(foo_cache, 7);

would become
+struct lc_element *e = lc_element_by_index(foo_cache, 7);
+struct foo *bar = lc_entry(e, struct foo, lc);

does that make sense?

any suggestions to split up the one vmalloc into several allocations?
kmalloc?  a bunch of zero order pages?
or are we reinventing the wheel?
(probably we do, anyways; but is that particular wheel already in kernel?)

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