Deutsch English Français Italiano |
<86cyjxwlcs.fsf@linuxsc.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!news.roellig-ltd.de!open-news-network.org!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch <tr.17687@z991.linuxsc.com> Newsgroups: comp.arch Subject: Re: fine points of dynamic memory allocation, not 80286 protected mode Date: Fri, 18 Oct 2024 07:12:51 -0700 Organization: A noiseless patient Spider Lines: 41 Message-ID: <86cyjxwlcs.fsf@linuxsc.com> References: <2024Oct6.150415@mips.complang.tuwien.ac.at> <d8cffb389b3fd055ee70e87da9a3403a@www.novabbs.org> <vep60r$2ck8s$1@dont-email.me> <868qunxjm5.fsf@linuxsc.com> <verl5q$1lsr$1@gal.iecc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Fri, 18 Oct 2024 16:12:55 +0200 (CEST) Injection-Info: dont-email.me; posting-host="6b29217a9f0925357c063ddd8fabd2b5"; logging-data="3516410"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX189qPgcrpaLfvOnv2IzfmR45/Z2hn4IWLE=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:TcWTEVKyzZTKY88WScabrCFr/0k= sha1:kHV4mSBAr+gm0qMiuOyTGSpVj/o= Bytes: 3368 John Levine <johnl@taugh.com> writes: > According to Tim Rentsch <tr.17687@z991.linuxsc.com>: > >> Once there is a way to get additional memory from whatever underlying >> environment is there, malloc() and free() can be implemented (and I >> believe most often are implemented) without needing to compare >> pointers. Note: pointers can be tested for equality without having >> to compare them relationally, and testing pointers for equality is >> well-defined between any two pointers (which may need to be converted >> to 'void *' to avoid a type mismatch). > > I suppose it's possible, but the versions I know keep free lists > and consolidate adjacent free chunks which requires comparing the > pointers. It might seem that way, but it isn't so. There is a fairly straightforward scheme -- using a single address-sized cell before each memory block -- that consolidates adjacent free chunks and maintains free lists, without needing to compare pointers (and in fact doesn't use pointers at all except for the free lists). Doing a malloc() needs to search an appropriate free list for an adequately large free block, and is constant time thereafter; doing a free() uses constant time, including consolidation of adjacent free chunks. For an implementation with 8-byte addresses, this can be done with a grain size of 16 bytes and a minimum of 32-byte blocks (of which 24 bytes can be used by the client). Coincidentally (or not) that matches the sizes I see in tests done on an Ubuntu Linux system (any size less than 25 uses 32 bytes, any size less than 41 uses 48 bytes, etc). The key insight is to use the preceding memory word to hold the size of this block plus two bits: bit A is one if this block is not free, and bit B is one if the previous block is not free. If bit B is zero (so the previous block is free) then the last word of the previous block holds the size of that block. Free lists are maintained using the first two words in each free block (of course plus the list headers, which is a small fixed overhead). This information is enough to combine adjacent free blocks when a free() is done.