From owner-freebsd-current@FreeBSD.ORG Mon Dec 12 03:31:17 2005 Return-Path: X-Original-To: current@freebsd.org Delivered-To: freebsd-current@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 38F8316A41F for ; Mon, 12 Dec 2005 03:31:17 +0000 (GMT) (envelope-from jasone@canonware.com) Received: from lh.synack.net (lh.synack.net [204.152.188.37]) by mx1.FreeBSD.org (Postfix) with ESMTP id 717FD43D58 for ; Mon, 12 Dec 2005 03:31:16 +0000 (GMT) (envelope-from jasone@canonware.com) Received: by lh.synack.net (Postfix, from userid 100) id 4EF0D5E48ED; Sun, 11 Dec 2005 19:31:16 -0800 (PST) Received: from [192.168.168.203] (moscow-cuda-gen2-68-64-60-20.losaca.adelphia.net [68.64.60.20]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by lh.synack.net (Postfix) with ESMTP id 9BD9D5E48A2; Sun, 11 Dec 2005 19:31:11 -0800 (PST) In-Reply-To: <439CEB74.9080505@acc.umu.se> References: <20051212014852.GA8775@shaka.acc.umu.se> <9FAD2B4B-C167-42D7-A8E7-BE03F4C07543@canonware.com> <439CEB74.9080505@acc.umu.se> Mime-Version: 1.0 (Apple Message framework v746.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: 7bit From: Jason Evans Date: Sun, 11 Dec 2005 19:27:39 -0800 To: Johan Bucht X-Mailer: Apple Mail (2.746.2) X-Spam-Checker-Version: SpamAssassin 3.0.4 (2005-06-05) on lh.synack.net X-Spam-Level: * X-Spam-Status: No, score=1.8 required=5.0 tests=RCVD_IN_NJABL_DUL, RCVD_IN_SORBS_DUL autolearn=no version=3.0.4 Cc: current@freebsd.org Subject: Re: New libc malloc patch X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 12 Dec 2005 03:31:17 -0000 On Dec 11, 2005, at 7:16 PM, Johan Bucht wrote: > Jason Evans wrote: >> >> On Dec 11, 2005, at 5:48 PM, Johan Bucht wrote: >>> * Saw you used a tree to look up the allocation sizes at free, this >>> * differs from how I and Solaris libumem does it. Instead I went for >>> * prepending a 8/16 byte tag containing the size of the >>> allocation for >>> * lockless size lookup. >> >> Actually, my implementation prepends a 4 byte tag that contains >> allocated/free flags, and the size of the allocation. The trees >> are only used to look up the sizes of huge allocations (> 8 MB on >> 32-bit platforms, and > 256 MB on 64-bit platforms). Huge >> allocations start at chunk boundaries, so prepending a tag would >> require an entire extra page (and would cause potentially serious >> external fragmentation on 32-bit systems). >> > Isn't 8 byte alignment expected by some applications? Yes, 8 or 16 byte alignment is expected (in fact I'm of the opinion that we should be using 16 byte alignment on i386 due to SSE2/SSE3). If I understand your question correctly, you're asking how I get away with 4 byte tags. Consider that (assuming 8-byte quantum) a malloc (16) call must actually be serviced by at least 24 bytes internally, in order to pad to the next quantum size. If I used 8 byte tags, then malloc(17) would require 32 bytes internally. By using 4 byte tags, malloc(13)..malloc(20) can be serviced by 24 bytes internally. At least one implementation (the OS X malloc implementation) uses 2 byte tags, but this has two problems: 1) unaligned memory access is slow on some architectures, and 2) it's too small to handle large object sizes, so a different allocation strategy has to be used starting at ~12 KB. > How do you know if a allocation is huge if you don't have a tag? I know an allocation is huge if its base address is chunk-aligned. The actual size is stored in a red-black tree node, which is allocated separately. Jason