From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60068.outbound.protection.outlook.com [40.107.6.68]) by sourceware.org (Postfix) with ESMTPS id 5D0633857C43 for ; Sat, 22 Aug 2020 19:40:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 5D0633857C43 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=thingsconnected.nl Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=maarten@thingsconnected.nl ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ZogEYeHjP40qo4SCkF9ozAgNkGmPsBqabo+fmcS8HEFI/zRSHsqCpVIlRnPt0AKbvmbeKTRePrpUACFUgUw6nQX17gZhOE3vl6TW7Xec16+wdTzt3xOQBDo2UsDUdFb0CO6PpXmwPKgC9tEFD0MauSoEN8ZEiYeeeZINT05uFB7WBsFjNzeWDSqJHUIvvLGsR352gBKgHyd+5nh/BKExlWlTFv7uk9j0b6v9g+erU+RXttsF9V7E91Anz/NW3SdvI4OSAYrgEPaI/n8MIkTIUSeD3gJn1rKmdGrIKnkTeyPSjwWsI8ro2OttlZj9SeXH+MiX5GDyIab5Exk2qYAeKA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=sp8/8KMKk+WSv5GkfwTR0htprpDxreCTJKsjPW5lY30=; b=WtU0l98a/t1AHoN/LkUBfxVRXKrKQmX9NDirk5lpiPDH0TdPuFb/UxDI+yFXLpprFaLTR+LPvKVXJQzHqqq0CDTENACIRMz3pTRDgi5p4hhWsk/Apemn/Q3gm8aKbimksRvv7nspuvFVUP/fK9TmLOr8eQxD/z27IVpQC1IlvFPOYT0EKIS9qNt9gprDsTknLHYV4outXPJ+giv4asJVsSxWL5xII13NmbKdyZiuhLRAz1o8Ucvm0YbX9bFYt22deafmTN584Uq78JAV/qXGdv54eMRsGxPmW7Va3WjQCJM9OoCQ7aG8YQPnGMPjUEUU7tS3nkO+7VVuAvCXRpKqLA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=thingsconnected.nl; dmarc=pass action=none header.from=thingsconnected.nl; dkim=pass header.d=thingsconnected.nl; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=hahei.onmicrosoft.com; s=selector2-hahei-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=sp8/8KMKk+WSv5GkfwTR0htprpDxreCTJKsjPW5lY30=; b=k8pJF4QvGx1TZUZCmVJuB5vxuyb59yOijEp3X555nOruO7U1VILrJDOkoW9kOei1OUPzh72BXI/a0q+pN2dSyZyMJ8xir1eNl+fs0WbYOOX+U7vD/Qtil113eTmWbGzLYKTL8tvyrqZZdPYzj5vfNGgjgThptwMi00zF3OZaKWU= Authentication-Results: sourceware.org; dkim=none (message not signed) header.d=none;sourceware.org; dmarc=none action=none header.from=thingsconnected.nl; Received: from VI1PR08MB3405.eurprd08.prod.outlook.com (2603:10a6:803:87::18) by VI1PR0801MB1805.eurprd08.prod.outlook.com (2603:10a6:800:58::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3305.25; Sat, 22 Aug 2020 19:40:11 +0000 Received: from VI1PR08MB3405.eurprd08.prod.outlook.com ([fe80::6d2f:1476:a62f:9cd1]) by VI1PR08MB3405.eurprd08.prod.outlook.com ([fe80::6d2f:1476:a62f:9cd1%3]) with mapi id 15.20.3305.025; Sat, 22 Aug 2020 19:40:11 +0000 To: newlib@sourceware.org From: Maarten van der Schrieck | Things Connected Subject: [PATCH] nano malloc allocator algorithm improvement Message-ID: Date: Sat, 22 Aug 2020 21:40:10 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US X-ClientProxiedBy: AM3PR07CA0136.eurprd07.prod.outlook.com (2603:10a6:207:8::22) To VI1PR08MB3405.eurprd08.prod.outlook.com (2603:10a6:803:87::18) MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 Received: from error.fritz.box (2001:981:e952:1:4c6a:378a:a24b:4e71) by AM3PR07CA0136.eurprd07.prod.outlook.com (2603:10a6:207:8::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3326.10 via Frontend Transport; Sat, 22 Aug 2020 19:40:11 +0000 X-Originating-IP: [2001:981:e952:1:4c6a:378a:a24b:4e71] X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 58916f90-07c4-47a9-4bb6-08d846d32f06 X-MS-TrafficTypeDiagnostic: VI1PR0801MB1805: X-Microsoft-Antispam-PRVS: X-MS-Oob-TLC-OOBClassifiers: OLM:8882; X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: eeJ31XM/kyO/EHlyGyDwD4X5KSLCV0AV89L10uC1xIPS9RK5ooab6Sq6kq0Vk1XpRHyR7qpTBqQB2dS0+fcNzqKaj3kLRepwUoF8Rs9lKuM+MWJpXt9/Or66tEIDy1KIUuOEHdsMdmLo6JueYaMYB4Gm1+OMbuuMrLvUJEYkQ6BSjtVKV++kB5FJw+ix6gJQtKI0VtIAiyhJip+mqQX3C8QAkg8gn4bO02yf3vhkKr8c7wonWHInvoxTj0aBHmBEAPGROlgzJz1WcgGy2v3e2vVjhTZXtIhMRr52IXalXGbblpMAqpLoaD2AYMMl1pJlA4oVki5nuBNjopoBNV/nlkzjkEGWt5LJ7j67C2oWFuvBGHmZn9/+eRhW9QmDgDvN X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1PR08MB3405.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(136003)(376002)(396003)(39830400003)(346002)(366004)(16526019)(186003)(31686004)(5660300002)(6506007)(8676002)(52116002)(8936002)(36756003)(6512007)(2906002)(83380400001)(478600001)(6486002)(66946007)(66476007)(2616005)(316002)(31696002)(6916009)(86362001)(66556008)(43740500002); DIR:OUT; SFP:1101; X-MS-Exchange-AntiSpam-MessageData: WsT0mu0jHj0hjbkDpkntfGytfSDbr2x3+nESPc3ltLUE/+Co54qx/QmAyPNWbsYnpj4RKBhNeilJ4UbM8LxQw28tA9N2XA1XUJCSxcMTLEHdCsEHCSlMOtAmLNJ8GWYGgApduMULF5axrKrHyKwUenAwA+xh0GuqjCRD2JuLDgNBucfFVVIPJuYJJQeLgkmTc8+8sAv7+DKIi2ksE0FXzFYPnkPN6QgusvGmjE+l1ghG9GjT6rUfkQBjUExXXU2pKlwReGaMtbWrsJHtm7T0d543I8ChIJawlhgvg+ddLyNd8M3Xw6VIufXw4XKXLvu0XuZoP6OAAhNj4/LCwcTlpVybrI13sF8yPu0gSsFUgKVb1HBfTnW6wpzyUbEQXSN6tVK6krDyc3a/89MYc5JZotlZykrm4y9rfIubLfM475g9ZdOfaR6RK34oqo6LwJ2wNBfS3aVkMnWZb20Zup8wKbjjxlMAHlPDHtV0HWB3RBly9Lv8oHXAgj93o7o9tnE1CS3QvdFPOGF+wM7pHoR6fpXEaww4pjYz+K6Fj+hipz8ST84ttghQkyhjGDhftX5Yn7p/3exPInzgpoIFtTxSZ7YcSVI/xxKt9D620YgLR8wuCLJp4MmzGOtPv9HKa+7eeAmspmxp94jycDkdoDpU7D/VFcrxLtavPSLl+2HbgTDAhlQyn2NDzC2rYGax9I8M3IiaaUeM73viHuW3MfayqA== X-OriginatorOrg: thingsconnected.nl X-MS-Exchange-CrossTenant-Network-Message-Id: 58916f90-07c4-47a9-4bb6-08d846d32f06 X-MS-Exchange-CrossTenant-AuthSource: VI1PR08MB3405.eurprd08.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 22 Aug 2020 19:40:11.6379 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 78d150be-2881-49f2-8b3c-54faded22572 X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: ocl+1OxzEwfwyUsDj6uZ3DuAhIA74Jkqt+Jgqk4wg9//TU1yso4k1IoqdXYd/vDVFW4EzvzinnN8/xmSanZTec1GsKd3Hu1ydgrYlRkcbZY= X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0801MB1805 X-Spam-Status: No, score=-11.1 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, MSGID_FROM_MTA_HEADER, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_PASS autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: newlib@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Newlib mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 22 Aug 2020 19:40:16 -0000 The current nano malloc implementation has two issues reducing the amount of memory available and increasing fragmentation. The first issue is that sbrk() will be called to allocate a space with the size of the entire requested alloc_size, even if the last free chunk borders the edge of currently allocated memory. This means that in a system with 20 kb of RAM, you will get ENOMEM when performing this: tmpbuf = malloc(10*1024); free(tmpbuf); tmpbuf2 = malloc(11*1024); // will fail on a 20 kb RAM system It would be better if malloc would detect if the last free chunk can be simply grown to alloc_size instead. (Or if free() would return the memory to the system by sbrk(-10kb), which is currently impossible.) The second issue is that a free chunk that is oversized will be cut up in two pieces, where the *second* piece is used for allocation and the first one is kept as a free chunk. Although this is easier/shorter in code (because the free list remains unaffected apart from the size of the free chunk) it leads to an inefficient pattern of memory allocation, and ultimately in fragmentation and slower malloc/free calls. As an example, again in a system with 20kb, if the above issue would be patched, you will still get ENOMEN when performing this: tmpbuf = malloc(10*1024); free(tmpbuf); tmpbuf2 = malloc(1); // this will end up in the middle of RAM space tmpbuf3 = malloc(15*1024); // will fail on a 20 kb RAM system Total impact on binary size (on ARM Thumb) is ~100 bytes. ---  newlib/libc/stdlib/nano-mallocr.c | 41 ++++++++++++++++++++++++++++---  1 file changed, 38 insertions(+), 3 deletions(-) diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c index 6ba0eb74b..9d3462861 100644 --- a/newlib/libc/stdlib/nano-mallocr.c +++ b/newlib/libc/stdlib/nano-mallocr.c @@ -258,15 +258,50 @@ void * nano_malloc(RARG malloc_size_t s)      while (r)      {          int rem = r->size - alloc_size; + +        /* To prevent a trailing but small chunk to be left unused, grow +         * the available memory and the chunk instead of allocating +         * alloc_size */ +        if (rem < 0 && r->next == NULL) +        { +            /* This is the last chunk, check if there is any allocated +             * memory after it. */ +            chunk *heap_end = sbrk_aligned(RCALL 0); +            if ((char *)r + r->size == heap_end) +            { +                /* Attempt to allocate the additional memory needed and +                 * go on as usual */ +                if (sbrk_aligned(RCALL -rem) == (void*)-1) +                { +                    RERRNO = ENOMEM; +                    MALLOC_UNLOCK; +                    return NULL; +                } +                rem = 0; +                r->size = alloc_size; +                /* Fall through to regular logic below */ +            } +        }          if (rem >= 0)          {              if (rem >= MALLOC_MINCHUNK)              {                  /* Find a chunk that much larger than required size, break -                * it into two chunks and return the second one */ -                r->size = rem; -                r = (chunk *)((char *)r + rem); +                 * it into two chunks and return the first one. +                 * Returning the second part would be a bit easier, because +                 * the chunk list stays intact, but doing that leads to +                 * memory fragmentation quickly. +                 */ +                chunk *part2 = (chunk *)((char *)r + alloc_size); +                part2->size = rem; +                part2->next = r->next;                  r->size = alloc_size; +                if ( p == r ) +                { +                    free_list = part2; +                } else { +                    p->next = part2; +                }              }              /* Find a chunk that is exactly the size or slightly bigger               * than requested size, just return this chunk */ -- 2.23.0