From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/13095 Path: news.gmane.org!.POSTED!not-for-mail From: Christopher Friedt Newsgroups: gmane.linux.lib.musl.general Subject: Re: malloc implementation survey: omalloc Date: Tue, 31 Jul 2018 10:49:53 -0400 Message-ID: References: <20180729192618.GA22386@voyager> <20180731074929.GB22386@voyager> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000008c28d105724cb118" X-Trace: blaine.gmane.org 1533048495 28508 195.159.176.226 (31 Jul 2018 14:48:15 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 31 Jul 2018 14:48:15 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-13111-gllmg-musl=m.gmane.org@lists.openwall.com Tue Jul 31 16:48:11 2018 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1fkVwY-0007JL-OR for gllmg-musl@m.gmane.org; Tue, 31 Jul 2018 16:48:10 +0200 Original-Received: (qmail 24001 invoked by uid 550); 31 Jul 2018 14:50:18 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 23980 invoked from network); 31 Jul 2018 14:50:17 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=1R5OUkCjamcG6NtWOgGLIhdHzcqClTsYy9ch6LHQ/TU=; b=lEh3spa8SPDQJtswGPMzmyYOf/wR7+m2CTqKQ6aJRyaxmEizGDTJNIIJogzthnXzdk deM7jb6u9eK4tJn2TzzK8VWS5PjKr2MKhAZ94g68gRHCMzRLyhZYJ5X+6a2NUO01Zlbb l6UpkDVEvXtlxR+REvHIW1ybJuFtCHoeYgFDzzlfYRQA1fITIsbcrF20PHzZQv6+50JE YQa4Nn2dL1FaudWsCfQfwpmZZXP3l+BrllyQAPzMgOg6wAc50L2rZAachlYA6si8J+EH YqX4PSpkCZ3yc1bYt4T0c0CaVHBjVbL064x0xfJHf6ubmEGwDSr4T/Dt8l8zhpNthhv6 bNQg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=1R5OUkCjamcG6NtWOgGLIhdHzcqClTsYy9ch6LHQ/TU=; b=uNb2NYQs3+fUHpzGBEteKRUqyncHc6rz6Run+ewR/eHxPw95mGSdciObiYfyclLVLc 0eewEusy1aa28/QfmcblRd2buEFruf1dxRxbTEk8OpgR1HFW9kafNxsM7MbCRWEpEETX gBsANzERYN+IaBczp2Un4U9dopNiqD7dyblAnJmcL16go9aLPTcKq4bZ4JF8Z0O/EWOa allQpZuJBv3sB61WaMnt9Pyw7iLwwjwKB4m+nCGHs/bOWL2V6NhWLhigSyXOB+YjBmwu lF/nJXqAjrBWBekMwYGK85xOLe0JthSbcbcB/1hO/wYDJJ2bYE/wNeOtWwCO0YGJmmK2 koIw== X-Gm-Message-State: AOUpUlEtEQE1lD71LythlE2mKHZMCfNqzy06B83EvfwmJMWh10Lfzcpv trv1epIdgSOTakdaNuZUKqTjCAhM9dTNBHI3/ch11g== X-Google-Smtp-Source: AAOMgpdYW+crDuLoWv99PqCyuYSv9CMdrh7/lxm4XuyRchDfDaX5fsNLi4wyW3VIBU9ThWuMiedk0TyX1Im+EMQIIhc= X-Received: by 2002:aca:ad4f:: with SMTP id w76-v6mr2084238oie.233.1533048605385; Tue, 31 Jul 2018 07:50:05 -0700 (PDT) In-Reply-To: <20180731074929.GB22386@voyager> Xref: news.gmane.org gmane.linux.lib.musl.general:13095 Archived-At: --0000000000008c28d105724cb118 Content-Type: text/plain; charset="UTF-8" On Tue, Jul 31, 2018, 3:49 AM Markus Wichmann, wrote: > On Mon, Jul 30, 2018 at 11:09:05AM -0400, Christopher Friedt wrote: > > I wrote it originally for using on the kernel-side of an rtos, but it > could > > easily be extended to make a syscall when a process runs out of ram. > > > > Obviously, a shortcoming is that the memory blocks must be PoT and there > is > > the potential for fragmentation. Otherwise though, the meta-information > is > > intrinsic within the pointer, which obliviates the need for external > > storage. > > > > That does sound interesting, but I don't really follow. The meta-info > which we need to save is the length of the object returned. How can you > encode that in the pointer without any external storage? Using internal > storage? Yeah, that is where we are right now, and that means there's > only one buffer overflow between us and oblivion at any given time. > > Or do you essentially have a large block of memory, with one area for > the 16-byte objects, one for the 32-byte ones, &c. But then what do you > do if your given area runs out and the application still wants more? https://en.wikipedia.org/wiki/Buddy_memory_allocation The 'bins' do overlap (e.g. a 64 byte chunk can also be used as 2 32-byte chunks or "buddies"), but their size (when using a bitmap for metadata) is encoded by the position of the bit in the map. This also encodes if a parent (or child) of a specific memory region is already in use or free. My original implementation was for an rtos with a compile-time-fixed memory size. In user space (since doubling ram usage is obviously bad) it would be best to use some container (e.g. an interval tree) to contain buddy-malloc nodes and general slabs of mmap. Current usage, a configurable fragmentation threshold, and the system pagesize, would determine if an allocation would use an existing buddy-malloc node, a new buddy-malloc node (PoT # of pages) or a sequence of pages. Pages would, of course, be allocated with mmap. I've personally not implemented malloc debugging for a buddy allocator though, since bits are precious enough, and there is no fundamental requirement for it, although technically, it would mean adding some padding with a computable bit pattern. I suppose if checking is enabled, it can be run before free(3) returns or before realloc(3) does anything. A global check on every function call would be more thorough, but obviously more expensive. --0000000000008c28d105724cb118 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


= On Tue, Jul 31, 2018, 3:49 AM Markus Wichmann, <nullplan@gmx.net> wrote:
On Mon, Jul 30, 2018 at 11:09:05AM -0400, Christopher Friedt wrote= :
> I wrote it originally for using on the kernel-side of an rtos, but it = could
> easily be extended to make a syscall when a process runs out of ram. >
> Obviously, a shortcoming is that the memory blocks must be PoT and the= re is
> the potential for fragmentation. Otherwise though, the meta-informatio= n is
> intrinsic within the pointer, which obliviates the need for external > storage.
>

That does sound interesting, but I don't really follow. The meta-info which we need to save is the length of the object returned. How can you
encode that in the pointer without any external storage? Using internal
storage? Yeah, that is where we are right now, and that means there's only one buffer overflow between us and oblivion at any given time.

Or do you essentially have a large block of memory, with one area for
the 16-byte objects, one for the 32-byte ones, &c. But then what do you=
do if your given area runs out and the application still wants more?


=
The 'bins' do overlap (e.g. a 64 byte chunk can a= lso be used as 2 32-byte chunks or "buddies"), but their size (wh= en using a bitmap for metadata) is encoded by the position of the bit in th= e map. This also encodes if a parent (or child) of a specific memory region= is already in use or free.

My original implementation was for an rtos with a compile-time-fixed me= mory size. In user space (since doubling ram usage is obviously bad) it wou= ld be best to use some container (e.g. an interval tree) to contain buddy-m= alloc nodes and general slabs of mmap. Current usage, a configurable fragme= ntation threshold, and the system pagesize, would determine if an allocatio= n would use an existing buddy-malloc node, a new buddy-malloc node (PoT # o= f pages) or a sequence of pages. Pages would, of course, be allocated with = mmap.

I've personall= y not implemented malloc debugging for a buddy allocator though, since bits= are precious enough, and there is no fundamental requirement for it, altho= ugh technically, it would mean adding some padding with a computable bit pa= ttern. I suppose if checking is enabled, it can be run before free(3) retur= ns or before realloc(3) does anything. A global check on every function cal= l would be more thorough, but obviously more expensive.
--0000000000008c28d105724cb118--