linux-ext4 - Re: ext2_find

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: <20080731162352.GE11632@mit.edu>
Date:	Thu, 31 Jul 2008 12:23:52 -0400
From:	Theodore Tso <tytso@....edu>
To:	Rohit Sharma <imreckless@...il.com>
Cc:	ext4 <linux-ext4@...r.kernel.org>
Subject: Re: ext2_find_near

On Thu, Jul 31, 2008 at 08:17:06PM +0530, Rohit Sharma wrote:
> What I understand from it is that it has something to do with reducing
> the chances of a concurrent allocation -- supposedly from a different
> PID.

Yes, that's exactly it.  To quote from from comment above the function:

 * In the latter case we colour the starting block by the callers PID to
 * prevent it from clashing with concurrent allocations for a different inode
 * in the same block group.

In computer science, the concept of "coloring" is to spread the
allocation across multiple (cpu's, processes, etc.) while
concentrating accesses from a specific CPU, processes, etc., in order
to provide better performance.  You will see references to coloring
pages for virtual memory systems, coloring slabs in slab allocators to
improve better cache utilization, etc.

When people talking using coloring to increase cache utilization, the
goal is to reduce the chances that cache collisions lead to premature
ejection of data from the cache.  In the case of block allocation, the
goal is that if you have two processes writing into the same directory
(for example, if you are compiling a program using "make -j4") that
they don't "collide" and start allocating blocks from the same
starting point, since that might result in an interleaved allocation
for the files.

What is going on here is that code is splitting the block group into
16 zones, and it using the low 4 bits of the process ID (i.e., pid %
16) to determine "zone" in the block group is used as a starting point
for the allocation.

This is a hueristic, and like all hueristics, in some cases it wins,
in other cases it is a lose.  Something like delayed allocation can do
a much better job than this particular hueristic.

					- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html