linux-kernel - Re: [RFCv2][PATCH] flexible array implementation

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] [day] [month] [year] [list]

Message-Id: <1248359401.24021.715.camel@nimitz>
Date:	Thu, 23 Jul 2009 07:30:01 -0700
From:	Dave Hansen <dave@...ux.vnet.ibm.com>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	vda.linux@...glemail.com, bblum@...gle.com,
	linux-kernel@...r.kernel.org,
	containers@...ts.linux-foundation.org, menage@...gle.com,
	akpm@...ux-foundation.org
Subject: Re: [RFCv2][PATCH] flexible array implementation

On Wed, 2009-07-22 at 19:45 -0700, H. Peter Anvin wrote:
> > I call it a flexible array.  It does all of its work in
> > PAGE_SIZE bits, so never does an order>0 allocation.
> > The base level has PAGE_SIZE-2*sizeof(int) bytes of
> > storage for pointers to the second level.  So, with a
> > 32-bit arch, you get about 4MB (4183112 bytes) of total
> > storage when the objects pack nicely into a page.  It
> > is half that on 64-bit because the pointers are twice
> > the size.
> 
> I'm wondering if there is any use case which would require scaling below
> the PAGE_SIZE level... in which case it would be nice for it to
> gracefully decay to a single kmalloc allocation + some metadata.

For the pid_t case that actually spawned all this, I think it makes a
ton of sense.  It should be pretty easy to just cannibalize the
base->part[] pointers to use for data if (total*element_size <=
bytes_allocated - sizeof(metadata)) in the base.  We'd have to store the
requested allocation total, but that's not bad.

1. Do we use this mode *only* when using a small 'total'?  Or, do we
   use the mode only when accessing a small range of elements, like
   indexes < 511.
2. Do we just use the mode when the indexes are large, but not sparse?
   Say, when someone is only using indexes 1024->1535?
3. Do we ever allocate less than 1 page (i.e. kmalloc(2048)) for the
   base given a small enough 'total' requested?  If so, it gets much
   harder to grow the array later on if we want to support resizing.
4. Do we ever promote under the covers from this mode up to the full
   two-level one?

This also gives us more of a reason to store a flex_array->total and
enforce that the array is not allowed to grow past that.

-- Dave

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