linux-kernel - Re: [PATCH] idr: Document ida tree sections

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: <20130813235133.GA3807@kmo-pixel>
Date:	Tue, 13 Aug 2013 16:51:33 -0700
From:	Kent Overstreet <kmo@...erainc.com>
To:	Tejun Heo <tj@...nel.org>
Cc:	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
	Stephen Rothwell <sfr@...b.auug.org.au>,
	Fengguang Wu <fengguang.wu@...el.com>
Subject: Re: [PATCH] idr: Document ida tree sections

On Tue, Aug 13, 2013 at 07:22:11PM -0400, Tejun Heo wrote:
> Hello,
> 
> On Tue, Aug 13, 2013 at 03:59:27PM -0700, Kent Overstreet wrote:
> > > Well, it's not necessarily about requiring it but more about surviving
> > > it with some grace when things don't go as expected, which is an
> > > important characteristic for common library stuff.
> > 
> > The patch I posted should solve the high order allocations stuff, and
> > sparseness from cyclic allocations was already solved.
> 
> I don't know.  Yeah, using vmalloc would be able to work around the
> issue for most cases, I suppose.  It's iffy to consume vmalloc space
> from ida, which functionally is such a basic algorithmic construct.
> It probably won't worsen things noticeably but vmalloc area can be a
> very precious resource on 32bit configs.

This is only using it for the array of pointers to sections though, not
the bitmap itself - and only when that allocations is > 16k. For INT_MAX
allocated ids (absolute worst case) we'd be using 256k of vmalloc memory
on 64 bit, half that on 32 bit.

> 
> > Whatever caching optimizations you do with a radix tree version I could
> > apply to this bitmap tree version, and my bitmap tree code is simpler
> > and _considerably_ faster than the existing code.
> 
> But the difference won't really matter.  Cached performance would be
> the same and that's likely to cover most cases, right?  It's not like
> radix tree is orders of magnitude slower.

Should probably be almost as good, yeah... in theory, but the space
efficiency still isn't going to be as good, and it'll probably be more
code... and at this point I really just don't want to futz with it more.
At this point unless there's something really wrong with this code I
just want to move onto something else :P
--
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/