From owner-freebsd-hackers@FreeBSD.ORG Tue Mar 2 03:52:37 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 1D6C6106566B for ; Tue, 2 Mar 2010 03:52:37 +0000 (UTC) (envelope-from dan@dan.emsphone.com) Received: from email1.allantgroup.com (email1.emsphone.com [199.67.51.115]) by mx1.freebsd.org (Postfix) with ESMTP id D7D048FC1E for ; Tue, 2 Mar 2010 03:52:36 +0000 (UTC) Received: from dan.emsphone.com (dan.emsphone.com [199.67.51.101]) by email1.allantgroup.com (8.14.0/8.14.0) with ESMTP id o223qXrN068939 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 1 Mar 2010 21:52:33 -0600 (CST) (envelope-from dan@dan.emsphone.com) Received: from dan.emsphone.com (smmsp@localhost [127.0.0.1]) by dan.emsphone.com (8.14.4/8.14.3) with ESMTP id o223qWoG007316 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 1 Mar 2010 21:52:33 -0600 (CST) (envelope-from dan@dan.emsphone.com) Received: (from dan@localhost) by dan.emsphone.com (8.14.4/8.14.3/Submit) id o223OfqW036895; Mon, 1 Mar 2010 21:24:41 -0600 (CST) (envelope-from dan) Date: Mon, 1 Mar 2010 21:24:40 -0600 From: Dan Nelson To: Shrivatsan Message-ID: <20100302032440.GV70798@dan.emsphone.com> References: <178848.53651.qm@web112006.mail.gq1.yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <178848.53651.qm@web112006.mail.gq1.yahoo.com> X-OS: FreeBSD 7.2-STABLE User-Agent: Mutt/1.5.20 (2009-06-14) X-Virus-Scanned: clamav-milter 0.95.3 at email1.allantgroup.com X-Virus-Status: Clean X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.0.2 (email1.allantgroup.com [199.67.51.78]); Mon, 01 Mar 2010 21:52:33 -0600 (CST) X-Scanned-By: MIMEDefang 2.45 Cc: freebsd-hackers@freebsd.org, shrivatsan@gmail.com Subject: Re: kernel malloc() and free() X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 02 Mar 2010 03:52:37 -0000 In the last episode (Mar 01), Shrivatsan said: > I am looking at the code that allocates and frees kernel memory. I > understand that allocating kernel memory is quite different from the user > level mallocs. In case of user level mallocs, we allocate requested size > + 4 bytes and store the requested size in the additional 4 bytes. Actually FreeBSD's userland malloc hasn't ever had a 4-byte-per-element overhead like this. All BSD mallocs have been block-based, where all objects in a page are the same size. The original bsd malloc had power-of-2 size groupings (blocks holding the same size objects were linked in a list). phkmalloc was imported in 1995 which moves the block metadata into a "page directory", which is separated from the memory returned by malloc(). The current malloc (jemalloc) has a similar setup but scales much better on SMP systems. http://phk.freebsd.dk/pubs/malloc.pdf http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf > However, in the case of kernel, allocating an additional 4 bytes is a > overhead since the request might fall in the next bucket. I looked into > the code and the documentation in the file uma_int.h, but I don't quite > understand the relation between slabs, zones and keg. How do we determine > the size of the memory that we are trying to free from given the virtual > address? I'm not too familiar with the kernel malloc, but it looks like each keg holds objects of the same size (and a keg may hold multiple slabs), so once you get a pointer to the slab header with the vtoslab() macro, slab->us_keg->uk_size points to the size of the allocation. Hm. Even after some reading, I'm not sure how the slabs keep track of which elements are allocated or free. I expected to find a bitmap somewhere that malloc() sets and free() clears, but I don't see it. Maybe some kernel hacker can explain it better :) Regardless, the size of the allocation at this point isn't important, since you know all the items in the page are the same size. -- Dan Nelson dnelson@allantgroup.com