From patchwork Tue Jun 8 20:30:46 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Heinrich Schuchardt X-Patchwork-Id: 1489628 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (no SPF record) smtp.mailfrom=lists.infradead.org (client-ip=2607:7c80:54:e::133; helo=bombadil.infradead.org; envelope-from=opensbi-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; secure) header.d=lists.infradead.org header.i=@lists.infradead.org header.a=rsa-sha256 header.s=bombadil.20210309 header.b=sONA9uFy; dkim=fail reason="signature verification failed" (1024-bit key; secure) header.d=gmx.net header.i=@gmx.net header.a=rsa-sha256 header.s=badeba3b8450 header.b=RhQ4EY1z; dkim-atps=neutral Received: from bombadil.infradead.org (bombadil.infradead.org [IPv6:2607:7c80:54:e::133]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G022L19jsz9s24 for ; Wed, 9 Jun 2021 06:31:21 +1000 (AEST) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:Message-Id:Date:Subject:Cc :To:From:Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References: List-Owner; bh=Js6Eg3qwratUJTLDqaTSC/jQUh/yz7HNKeXwH8zVKN8=; b=sONA9uFyOkSoR7 Y6zqnwHgqqvODjNvZ5oyb51rWbDHkY2orwkKtCBfUjIDtg7by3uSZPM0YLF+u9eTdRImFZr1jzsSQ DGv3ESgjE1dJqHWAXliRKFT0RkVaEeU5+StDpBe+2E+sdQHJv9k6lDAl30/F3slfsI/eD9YDVaMtr j/EIwL10b2jWBh0HOofIudhOydCtmkGUPNs6r3h6Ty3gZ/fchHsXq826fEvpDv5H86eX/7D3Mm8h/ 8WkHT17peQHNQjJS/IB//ibFHxmufufU3dm1Ysw4t4YZaHCIRZb29SV05C8Pn5fm+UvHCmjW7ZA5C BeIFFSfMnHDWtCanpVdw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1lqiNY-00APqi-D3; Tue, 08 Jun 2021 20:31:16 +0000 Received: from mout.gmx.net ([212.227.17.22]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1lqiNS-00APpo-Hh for opensbi@lists.infradead.org; Tue, 08 Jun 2021 20:31:14 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=gmx.net; s=badeba3b8450; t=1623184265; bh=1tWRj9F7KgB7f/Hyuz4Tg2yRunVSWAZkBve3QiSYV+0=; h=X-UI-Sender-Class:From:To:Cc:Subject:Date; b=RhQ4EY1z2Iw89I4BnBOJDrvIMCJJY44oMeHwHU6C4mtsRgd4nqWTQIUkaQ7eV27L9 Pgan4ruOc9R+zqzuSPVwZ+lwSNo+iVboMp7aDTnls1OtC3ns3BjMKNp5oWPrcQJFuc 2acYdPzbUXJb/fDuqOdU5rCkLTRGgtT3b/Pc/ipc= X-UI-Sender-Class: 01bb95c1-4bf8-414a-932a-4f6e2808ef9c Received: from LT02.fritz.box ([62.143.247.63]) by mail.gmx.net (mrgmx105 [212.227.17.174]) with ESMTPSA (Nemesis) id 1N8GQy-1lLjAn147s-014GbZ; Tue, 08 Jun 2021 22:31:05 +0200 From: Heinrich Schuchardt To: opensbi@lists.infradead.org Cc: Anup Patel , Atish Patra , Heinrich Schuchardt Subject: [PATCH 1/1] lib: sbi_scratch: re-implement scratch memory allocator Date: Tue, 8 Jun 2021 22:30:46 +0200 Message-Id: <20210608203046.105890-1-xypron.glpk@gmx.de> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 X-Provags-ID: V03:K1:l4VvSs0GzR7LYgNQJdj+v6g4D+S2vvNAQM930Ko6vclFVLVUKMt jp2O2XucKQnhBfxG0XmV7I/jPJcxADzpNENB3LmJlPGaiiuZLS8t/A6YEyxvz+dWlQqBzXB oncdQt6ZeZlp3iGev9gUbr5PWCkgRe0vV31ic7is2TNOhuuivvkdP2gpk1O4wQbZvZ7iBED n94IE9Oy2cr0/wX7+SgVQ== X-Spam-Flag: NO X-UI-Out-Filterresults: notjunk:1;V03:K0:Ow4oJBl2xeg=:svDkW9YDnitSqU6FNbZjL2 v+S2IrlZXEqZXeZS4eB5fohm+M4gAB6GB1i+U72joJ/ZlLymwSIYxWuUFvPEi47Hv2L01Tw5x 6/NO7Vu2r0E7o4O4EI2k17bfSvkYoQTA5k00nnhRmKxaTWfMNHXmGqIxb4OXVStPgWWQqBnrM 3IY+JQzyJlr87IHR99JdjfwsaWA7EOpFHotgfHNIjjS8drbZCR0N+Ax3KNiGWpp1k37JNywX2 PVmyjF3dtAT9Jw/ygm39hhfLZw2s2ZgsNI2++BCdEKTNHjjIzwKyxd5n8RcBZq1pJg7C4Fsdq LPVGHXgVAYc31me7zNM4BJCo2HhX1pf12LlMfDcodIPWu/2fUgVSyq/LiSq0K+7ti/lsHR67m qMBgCm9QP3mLYT05bxqAf4KDZ8joj3iwK/5CDEdy2xvRSgJ/T24tjZLL9HvSjENh50NwNxfE5 /XPsXr66vcooLygJ59eJdJWgWgSZAP0itxRhi0JtI4uff1o5KYQOE6IY+g46zQpDB+onLzhLP v35Dw8jOwOKZEYwVVFL+27LTXP6F1bAjX29HpDtoZaykBvbElqgslUeaekbyHsW6SFEUaGq3V F8tq27GozRnA7VTxFpJxfstzm5kSQ+h2OGBOqwaJAf5NImKsxZB2s9zlRrEaxVXtY29Y9Jw1K WfWZtQ+0BTv/+Sax5QFlqOinSmKvEizgFugGSCCYGBWpFiNlaPyZsBr4K9wF9JhY8OZsRQdzX ovn+bOIiJnCMwdonNdOJNRMeErQf3jzEZZSssn2IXomP18jsjpRJ4timVc99UafOF9iDqYilu wylE8SmV5c2uS2ZvdSvxeJuTH5u1t0WNLoGgiV1RuF39sHjDxMmgA72UN5yJXKUgZTzgOUEaP HTtVLb44cpoO6WCt4rgGnN+I3a03UvycAqk6LUWd69Q2/hHynDwiN0pGzi+AmMfxCHlBHf6lw Vk1lrj4MsCyzX+3qdEYEyf6h7L0mkVcNicyHgG0oRcvZdQcFjkR4mpEfedDmxkqIVn7ejLgzG APAVhWwHeXrrRcqMQsM2VI1CmJQ7JamvJlHZiKHgGm1VjEK4/2GLOpDVGzli5iLCM9f8L6HrG nuw1Nne2PCyBxGSDkanM6meHajtEJAO8Dlk X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210608_133110_906835_FE96462C X-CRM114-Status: GOOD ( 26.31 ) X-Spam-Score: 0.0 (/) X-Spam-Report: Spam detection software, running on the system "bombadil.infradead.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Up to now we could allocated scratch memory but not deallocate it. Provide a best fit memory allocator. Signed-off-by: Heinrich Schuchardt --- include/sbi/sbi_scratch.h | 52 +++++++++- include/sbi/sbi_types.h | 2 + lib/sbi/sbi_scratch.c | 203 +++++++++++++++++++++++++++++++------- 3 files changed, 218 [...] Content analysis details: (0.0 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [212.227.17.22 listed in list.dnswl.org] 0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [212.227.17.22 listed in wl.mailspike.net] 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record -0.0 SPF_PASS SPF: sender matches SPF record 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider [xypron.glpk[at]gmx.de] -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid 0.0 RCVD_IN_MSPIKE_WL Mailspike good senders X-BeenThere: opensbi@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "opensbi" Errors-To: opensbi-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org Up to now we could allocated scratch memory but not deallocate it. Provide a best fit memory allocator. Signed-off-by: Heinrich Schuchardt --- include/sbi/sbi_scratch.h | 52 +++++++++- include/sbi/sbi_types.h | 2 + lib/sbi/sbi_scratch.c | 203 +++++++++++++++++++++++++++++++------- 3 files changed, 218 insertions(+), 39 deletions(-) -- 2.30.2 diff --git a/include/sbi/sbi_scratch.h b/include/sbi/sbi_scratch.h index 186a40c..f9ea434 100644 --- a/include/sbi/sbi_scratch.h +++ b/include/sbi/sbi_scratch.h @@ -36,10 +36,10 @@ #define SBI_SCRATCH_TMP0_OFFSET (9 * __SIZEOF_POINTER__) /** Offset of options member in sbi_scratch */ #define SBI_SCRATCH_OPTIONS_OFFSET (10 * __SIZEOF_POINTER__) -/** Offset of extra space in sbi_scratch */ -#define SBI_SCRATCH_EXTRA_SPACE_OFFSET (11 * __SIZEOF_POINTER__) /** Maximum size of sbi_scratch (4KB) */ #define SBI_SCRATCH_SIZE (0x1000) +/** Offset of field mem in the sbi_mem_alloc structure */ +#define SBI_SCRATCH_ALLOC_SIZE (offsetof(struct sbi_scratch_alloc, mem)) /* clang-format on */ @@ -47,6 +47,49 @@ #include +/** + * struct sbi_scratch_alloc - memory allocation + * + * This structure describes a block of allocated or free memory. + * The fields @prev and @next are only used for free blocks. + */ +struct sbi_scratch_alloc { + /** + * @prev_size: size of previous memory block + * + * If the bit 0 is zero the memory is available. + * If the bit 0 is non-zero the memory is allocated. + */ + unsigned int prev_size; + /** + * @size: size of memory block + * + * If the bit 0 is zero the memory is available. + * If the bit 0 is non-zero the memory is allocated. + */ + unsigned int size; + + union { + /** + * @mem: allocated memory + * + * The macro SBI_SCRATCH_ALLOC_SIZE provides the offset of @mem + * in the sbi_mem_alloc structure. + */ + unsigned char mem[0]; + struct { + /** + * @prev: offset of preceeding block in free block list + */ + unsigned int prev; + /** + * @next: offset of succceeding block in free block list + */ + unsigned int next; + }; + }; +} __aligned(2 * sizeof(int)); + /** Representation of per-HART scratch space */ struct sbi_scratch { /** Start (or base) address of firmware linked to OpenSBI library */ @@ -71,6 +114,8 @@ struct sbi_scratch { unsigned long tmp0; /** Options for OpenSBI library */ unsigned long options; + /** Start of scratch memory allocation list */ + struct sbi_scratch_alloc mem; }; /** Possible options for OpenSBI library */ @@ -95,8 +140,7 @@ int sbi_scratch_init(struct sbi_scratch *scratch); /** * Allocate from extra space in sbi_scratch * - * @return zero on failure and non-zero (>= SBI_SCRATCH_EXTRA_SPACE_OFFSET) - * on success + * @return zero on failure and non-zero on success */ unsigned long sbi_scratch_alloc_offset(unsigned long size); diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h index 38e3565..2050265 100644 --- a/include/sbi/sbi_types.h +++ b/include/sbi/sbi_types.h @@ -88,6 +88,8 @@ typedef unsigned long physical_size_t; #define STR(x) XSTR(x) #define XSTR(x) #x +#define ALIGN(x, a) ((typeof(x))((unsigned long)(x + (a - 1)) & ~(a - 1))) + #define ROUNDUP(a, b) ((((a)-1) / (b) + 1) * (b)) #define ROUNDDOWN(a, b) ((a) / (b) * (b)) diff --git a/lib/sbi/sbi_scratch.c b/lib/sbi/sbi_scratch.c index 87b34c6..4c59c62 100644 --- a/lib/sbi/sbi_scratch.c +++ b/lib/sbi/sbi_scratch.c @@ -18,10 +18,16 @@ u32 last_hartid_having_scratch = SBI_HARTMASK_MAX_BITS - 1; struct sbi_scratch *hartid_to_scratch_table[SBI_HARTMASK_MAX_BITS] = { 0 }; static spinlock_t extra_lock = SPIN_LOCK_INITIALIZER; -static unsigned long extra_offset = SBI_SCRATCH_EXTRA_SPACE_OFFSET; +static unsigned int first_free; typedef struct sbi_scratch *(*hartid2scratch)(ulong hartid, ulong hartindex); +/** + * sbi_scratch_init() - initialize scratch table and allocator + * + * @scratch: pointer to table + * Return: 0 on success + */ int sbi_scratch_init(struct sbi_scratch *scratch) { u32 i; @@ -37,63 +43,190 @@ int sbi_scratch_init(struct sbi_scratch *scratch) last_hartid_having_scratch = i; } + /* Initialize memory allocation block list */ + scratch = sbi_hartid_to_scratch(last_hartid_having_scratch); + + scratch->mem.prev_size = (2 * sizeof(unsigned int)) | 1U; + scratch->mem.size = SBI_SCRATCH_SIZE - + offsetof(struct sbi_scratch, mem.mem); + first_free = offsetof(struct sbi_scratch, mem); + scratch->mem.prev = 0; + scratch->mem.next = 0; + return 0; } +/** + * sbi_scratch_alloc_offset() - allocate scratch memory + * + * @size: requested size + * Return: offset of allocated block on succcess, 0 on failure + */ unsigned long sbi_scratch_alloc_offset(unsigned long size) { - u32 i; - void *ptr; - unsigned long ret = 0; - struct sbi_scratch *rscratch; + unsigned long ret; + unsigned int best_size = ~0U; + struct sbi_scratch_alloc *best = NULL; + struct sbi_scratch *scratch = + sbi_hartid_to_scratch(last_hartid_having_scratch); + unsigned int next; + struct sbi_scratch_alloc *current; + struct sbi_scratch_alloc *pred, *succ; + struct sbi_scratch_alloc *end = + (void *)((char *)scratch + SBI_SCRATCH_SIZE); /* - * We have a simple brain-dead allocator which never expects - * anything to be free-ed hence it keeps incrementing the - * next allocation offset until it runs-out of space. - * - * In future, we will have more sophisticated allocator which - * will allow us to re-claim free-ed space. + * When allocating zero bytes we still need space + * for the prev and next fields. */ - if (!size) + size = 1; + size = ALIGN(size, 2 * sizeof(unsigned int)); + + spin_lock(&extra_lock); + + /* Find best fitting free block */ + for (next = first_free; next; next = current->next) { + current = (void *)((char *)scratch + next); + if (current->size > best_size || current->size < size) + continue; + best_size = current->size; + best = current; + } + if (!best) { + spin_unlock(&extra_lock); return 0; + } - if (size & (__SIZEOF_POINTER__ - 1)) - size = (size & ~(__SIZEOF_POINTER__ - 1)) + __SIZEOF_POINTER__; + /* Update free list */ + if (best->prev) + pred = (void *)((char *)scratch + best->prev); + else + pred = NULL; + if (best->next) + succ = (void *)((char *)scratch + best->next); + else + succ = NULL; + + if (best->size > size + SBI_SCRATCH_ALLOC_SIZE) { + /* Split block, use the lower part for allocation. */ + current = (struct sbi_scratch_alloc *)&best->mem[size]; + next = (char *)current - (char *)scratch; + current->size = best->size - size - + SBI_SCRATCH_ALLOC_SIZE; + current->prev = best->prev; + current->next = best->next; + current->prev_size = size | 1U; + best->size = size; + if (succ) + succ->prev = next; + } else { + next = best->next; + if (succ) + succ->prev = best->prev; + current = best; + } - spin_lock(&extra_lock); + if (pred) + pred->next = next; + else + first_free = next; - if (SBI_SCRATCH_SIZE < (extra_offset + size)) - goto done; + /* Update memory block list */ + succ = (struct sbi_scratch_alloc *)¤t->mem[current->size]; - ret = extra_offset; - extra_offset += size; + best->size |= 1U; -done: - spin_unlock(&extra_lock); + if (succ < end) + succ->prev_size = current->size; - if (ret) { - for (i = 0; i <= sbi_scratch_last_hartid(); i++) { - rscratch = sbi_hartid_to_scratch(i); - if (!rscratch) - continue; - ptr = sbi_scratch_offset_ptr(rscratch, ret); - sbi_memset(ptr, 0, size); - } + ret = best->mem - (unsigned char *)scratch; + + /* Erase allocated scratch memory */ + for (unsigned int i = 0; i <= last_hartid_having_scratch; i++) { + void *ptr; + struct sbi_scratch *rscratch; + + rscratch = sbi_hartid_to_scratch(i); + if (!rscratch) + continue; + ptr = sbi_scratch_offset_ptr(rscratch, ret); + sbi_memset(ptr, 0, size); } + spin_unlock(&extra_lock); + return ret; } +/** + * sbi_scratch_free_offset() - free scratch memory + * + * @offset: offset to memory to be freed + */ void sbi_scratch_free_offset(unsigned long offset) { - if ((offset < SBI_SCRATCH_EXTRA_SPACE_OFFSET) || - (SBI_SCRATCH_SIZE <= offset)) + struct sbi_scratch *scratch = + sbi_hartid_to_scratch(last_hartid_having_scratch); + struct sbi_scratch_alloc *freed = (void *)((unsigned char *)scratch + + offset - SBI_SCRATCH_ALLOC_SIZE); + struct sbi_scratch_alloc *pred, *succ; + struct sbi_scratch_alloc *end = + (void *)((char *)scratch + SBI_SCRATCH_SIZE); + + spin_lock(&extra_lock); + + if (!offset || !(freed->size & 1U)) { + spin_unlock(&extra_lock); return; + } - /* - * We don't actually free-up because it's a simple - * brain-dead allocator. - */ + /* Mark block as free */ + freed->size &= ~1U; + + pred = (struct sbi_scratch_alloc *)((char *)freed - + (freed->prev_size & ~1U) - SBI_SCRATCH_ALLOC_SIZE); + if (pred >= &scratch->mem && !(pred->size & 1U)) { + /* Coalesce free blocks */ + pred->size += freed->size + SBI_SCRATCH_ALLOC_SIZE; + freed = pred; + } else { + /* Insert at start of free list */ + if (first_free) { + succ = (void *)((char *)scratch + first_free); + succ->prev = offset - SBI_SCRATCH_ALLOC_SIZE; + } + freed->next = first_free; + freed->prev = 0; + first_free = offset - SBI_SCRATCH_ALLOC_SIZE; + } + + succ = (struct sbi_scratch_alloc *)&freed->mem[freed->size & ~1U]; + if (succ < end) { + if (!(succ->size & 1U)) { + struct sbi_scratch_alloc *succ2; + + /* Coalesce free blocks */ + succ2 = (struct sbi_scratch_alloc *) + &succ->mem[succ->size & ~1U]; + freed->size += SBI_SCRATCH_ALLOC_SIZE + succ->size; + if (succ2 < end) + succ2->prev_size = freed->size; + + /* Remove successor from free list */ + if (succ->prev) { + pred = (void *)((char *)scratch + succ->prev); + pred->next = succ->next; + } else { + first_free = succ->next; + } + if (succ->next) { + succ2 = (void *)((char *)scratch + succ->next); + succ2->prev = succ->prev; + } + } else { + succ->prev_size = freed->size; + } + } + spin_unlock(&extra_lock); }