linux-kernel - Re: [PATCH 0/3] staging: zcache: xcfmalloc support

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]

Date:	Thu, 01 Sep 2011 16:44:23 -0700
From:	Dave Hansen <dave@...ux.vnet.ibm.com>
To:	Seth Jennings <sjenning@...ux.vnet.ibm.com>
Cc:	Dan Magenheimer <dan.magenheimer@...cle.com>, gregkh@...e.de,
	devel@...verdev.osuosl.org, ngupta@...are.org,
	cascardo@...oscopio.com, rdunlap@...otime.net,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 0/3] staging: zcache: xcfmalloc support

On Thu, 2011-09-01 at 17:01 -0500, Seth Jennings wrote:
> I was seeing n as the number of allocations.  Since 
> XCF_MAX_BLOCKS_PER_ALLOC and XCF_NUM_FREELISTS are constant (i.e.
> not increasing with the number of allocations) wouldn't it be
> O(1)?

It's the difference between your implementation and the _algorithm_
you've chosen.  If someone doubled XCF_MAX_BLOCKS_PER_ALLOC and
XCF_NUM_FREELISTS, you'd see the time quadruple, not stay constant.
That's a property of the _algorithm_.

> > xcfmalloc's big compromise is that it doesn't do any searching or
> > fitting.  It might needlessly split larger blocks when two small ones
> > would have worked, for instance.
> 
> Splitting a larger block is the last option.  I might not
> be understanding you correctly, but find_remove_block() does try to
> find the optimal block to use, which is "searching and fitting" in my
> mind.

I don't want to split hairs on the wording.  It's obvious, though, that
xcfmalloc does not find _optimal_ fits.  It also doesn't use the
smallest-possible blocks to fit the alloction.  Consider if you wanted a
1000 byte allocation (with 10 100-byte buckets and no metadata for
simplicity), and had 4 blocks:

        900
        500,500,500

I think it would split a 500 into 100,400, and leave the 400:

        500,500
        400

It took the largest (most valuable) block, and split a 500 block when it
didn't have to.  The reason it doesn't do this is that it doesn't
_search_.  It just indexes and guesses.  That's *fast*, but it errs on
the side of speed rather than being optimal.  That's OK, we do it all
the time, but it *is* a compromise.  We should at least be thinking of
the cases when this doesn't perform well.

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