From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 71597 invoked by alias); 6 Mar 2018 20:42:51 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Received: (qmail 71575 invoked by uid 89); 6 Mar 2018 20:42:50 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-5.6 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_1,SPF_NEUTRAL autolearn=ham version=3.3.2 spammy=H*F:D*seznam.cz, reserved, HContent-Transfer-Encoding:8bit X-HELO: popelka.ms.mff.cuni.cz Date: Tue, 06 Mar 2018 20:42:00 -0000 From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= To: libc-alpha@sourceware.org Subject: best-fit algorithm with bitmap heap Message-ID: <20180306204243.GA19518@domone> References: <20180301213318.GB3062@domone> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20180301213318.GB3062@domone> User-Agent: Mutt/1.5.20 (2009-06-14) X-SW-Source: 2018-03/txt/msg00159.txt.bz2 On Thu, Mar 01, 2018 at 10:33:18PM +0100, Ondřej Bílka wrote: > Like I mentioned in other thread I plan to make improved malloc+friends. > It will be split to several aspects. > I got idea when I pondered about merging chunks and deleting old data that you don't have to delete them from data structure. It requires to save data about free chunks separately and data to check if chunk information is up-to-date. To limit space usage one would need to use fixed size buffer with these, when its full one needs to delete all invalid entries from buffer, and add/remove elements from bigger storage to make buffer half full. I could do this quickly with bitmaps and some conditions for sake of simplicity. 1. It would consider only allocation where capacity is 1-16 integer multiple of block 2. Data would be in 64-block pages where first and last block are reserved by allocator. As data structure for page start of allocated chunk would be denoted by 1 in corresponding bit of alloc_first and end in corresponding bit of alloc_last. Reserved blocks are there to put sentinel 1 at end of bitmaps. For faster operations bits in alloc_first could be in reversed order. When one has address and capacity of b blocks testing if it is valid free area is easy, from address we determine header and number s of starting block. First we check that free space starts there with formula (alloc_last & (1<<(s-1))) To test that it is free space until s+b which should be start of chunk it should be formula like this(maybe its off by one somewhere, didn't test that) ((alloc_first>>s)<<(64-b)) == 1<<63 On free with offset s one zeroes allocated bits with alloc_first = alloc_first ^ (1<