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

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

Message-ID: <20090503062720.GA31340@racke>
Date:	Sun, 3 May 2009 08:27:20 +0200
From:	Lars Ellenberg <lars.ellenberg@...bit.com>
To:	Kyle Moffett <kyle@...fetthome.net>
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>,
	Bart Van Assche <bart.vanassche@...il.com>
Subject: Re: [PATCH 02/16] DRBD: lru_cache

On Sat, May 02, 2009 at 07:51:36PM -0400, Kyle Moffett wrote:
> After digging through this a bit, I would recommend rewriting this
> whole part.  The part that definitely needs to go is the vmalloc() of
> your whole LRU at once.
> 
> Here's some code I've been fiddling around with for a while.  It uses
> a kmem_cache and a shrinker callback (although it does need a small
> patch to the shrinker code) to provide a dynamically sized LRU list
> for fixed-size objects.

Thanks.

When we created our lru_cache stuff, we considered embedding callbacks
and internal locking, but decided against it.  Conceptually it should be
more like the "list.h" list handling infrastructure.

The user will have their own locking in place anyways, and in general
their critical section will be a few lines of code larger than the
"lru cache" manipulation itself.

And, the specific use of our implementation is that there is a
pre-selected maximum count of in-use objects, and the user gets
feedback about changes to this "active" set of objects.

Think of a small room with N seats, and one entrance.
Any number of people outside.
Only N fit in the room.
Seats are numbered (index), people have id (element number).

Our lru_cache implementation is the man at the door,
keepeing track of which seats are empty,
and seeing to it that if one needs to go in,
either there is an empty seat available,
or first the "most dispensable" one gets out.

That is where the focus is:
make the set of active objects easily trackable.
So one can easily keep track of who is in, and who is not,
by writing a log of just this "diff":
seat index was occupied by element_nr A, but now is by element_nr B.

The lru part is to make it more easy to determine
who the "most dispensable" is.

So from looking at your code, it may be fine for the "lru" part,
but it is not suitable for our purposes.

	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/