linux-kernel - Re: [PATCH v3 next/akpm] aio: convert the ioctx list to radix tree

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: <20130612194005.GC8389@lenny.home.zabbo.net>
Date:	Wed, 12 Jun 2013 12:40:05 -0700
From:	Zach Brown <zab@...hat.com>
To:	Benjamin LaHaise <bcrl@...ck.org>
Cc:	Kent Overstreet <koverstreet@...gle.com>,
	Octavian Purdila <octavian.purdila@...el.com>,
	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
	linux-aio@...ck.org, linux-s390@...r.kernel.org,
	schwidefsky@...ibm.com, kirill.shutemov@...ux.intel.com,
	Andi Kleen <ak@...ux.intel.com>
Subject: Re: [PATCH v3 next/akpm] aio: convert the ioctx list to radix tree

> I've got an alternate approach for fixing this wart in lookup_ioctx()...  
> Instead of using an rbtree, just use the reserved id in the ring buffer 
> header to index an array pointing the ioctx.  It's not finished yet, and 
> it needs to be tidied up, but is most of the way there.

Yeah, that might work.

Note that the patch wasn't using an rbtree, it was storing the pointer
value in a *radix* which is why single lookups took so long.  Presumably
radix was used for RCU lookups.

Your ring->id trick lets us use RCU with small ints instead of the
context pointer.  It might be worth using idr instead of rolling manual
array code.  It'd still be much faster than the list, but get rid of the
large alloc, array walking, memcpy(), etc.

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