From nobody Fri Feb 3 15:50:35 2023 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4P7g981ycpz3kRwx; Fri, 3 Feb 2023 15:50:36 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (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 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4P7g980xQrz3HKQ; Fri, 3 Feb 2023 15:50:36 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1675439436; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=H2RfOmE0N/4pwIw2zBWmQkl1stZPML3thmXsaWFI76Q=; b=I79j3MYrQjTZtfXFIgIoWCSmOSO1WfY4QLShTSLsXAxI1k6iDZZdtAvSPPnLSky/WXNc1W KRQmrBPfLLQ7sNA9dE902jojQGHGAVBQtmBGNkvbTh54XeyzI4hT/MP+Pw27ZrDKeBib91 DU8k4M4yDcLOadDINDY4g3frJT+BDr+bZkXhd71JnsFhtVjL+SjNXg4YDt4nQdd9NsTkAB 3zs+2Wmq3wNSVdiQiIhQOk8TkRjZw2SjX8k4F+jAUUU6xsxFx7KWgfxpO+k5YIjUlSE+Hm jiUtVpsk1E6t2aHCo9fZsLt+VTDJMUfZHteEYNIku0kljxFvlWGFVco5Yb5j/Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1675439436; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=H2RfOmE0N/4pwIw2zBWmQkl1stZPML3thmXsaWFI76Q=; b=QoZ3xhT2DOZbITH6Z/GJqgDZCLGp+LsFqfl+B4QzUDzyvVRa62tDFBDmni+gNaBXKFXbMC 6pXsD2r6yLiSLufqzIKrH9O7BKhUcZtCcEfSF1DaIIDV9A5Ri+HGniFdTrJ3o4vhQQkH9y RoqRiB5xgn40gl/n2AMkMqtxxvcMeBxpDo601FKVtyH6nmklGejZe8vNKGH8LYfeXKV2HR lQlMrO8BN6zQ/BSizDH881Hj3YshhYJTLMmF1Zdj/Kq2hz2RLnS+0P9xNGIdDzrXv7muZy 0U41ckteKMeugEUJwmmrL389JBAZEVVqBQ/TLBLJLjH/r5s963havhSQUBlXQQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1675439436; a=rsa-sha256; cv=none; b=WndXKDyia7tTskV5KlS1o0CvImZRTNMCwW0UBMrRaCzIzbig05B+z+vUbRBv6TKCunRibH gUg9zgqp5Av8pZIXAmkPGR0ruPUc28vutV85XWvga8T51OycDHVsc17aBXW9CS0cqvUAT5 xt+l1d9IrBzkQyLaHTdfcKXUh/YCw1PvILE6ZpFiZ+P5Dcj6Y95CqQ+rcajBinr4Q6zvNm nLTlcmiJR95fPy9Z7fbhE1JMHndgZpnDxlt16y8f8KgyWaNyTzoHMBALRBCjkkkpz36np9 HnqAt8jUV4kCHcBSnRCuDaqjt3AKXqIp6Br+FnkNekklxm+QgacdD+4aCWRFKw== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (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) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4P7g9802Ynzg81; Fri, 3 Feb 2023 15:50:36 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 313FoZGI022933; Fri, 3 Feb 2023 15:50:35 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 313FoZ0k022932; Fri, 3 Feb 2023 15:50:35 GMT (envelope-from git) Date: Fri, 3 Feb 2023 15:50:35 GMT Message-Id: <202302031550.313FoZ0k022932@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Warner Losh Subject: git: 08779e839ac1 - main - kboot: Create segment handling code at main level List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: imp X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 08779e839ac11c410d314ce225e2246ac4d2e8c0 Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by imp: URL: https://cgit.FreeBSD.org/src/commit/?id=08779e839ac11c410d314ce225e2246ac4d2e8c0 commit 08779e839ac11c410d314ce225e2246ac4d2e8c0 Author: Warner Losh AuthorDate: 2023-02-03 15:37:53 +0000 Commit: Warner Losh CommitDate: 2023-02-03 15:41:39 +0000 kboot: Create segment handling code at main level Create segment handling code up to the top level. Move it all into seg.c, and make necessary adjustments for it being in a new file, including inventing print_avail() and first_avail() to print the array and find the first large enough memory hole. aarch64 will use this, and I'll refactor the other platforms to use it as I make them work. Sponsored by: Netflix Discussed with: kevans Differential Revision: https://reviews.freebsd.org/D38308 --- stand/kboot/Makefile | 1 + stand/kboot/kboot.h | 8 +++ stand/kboot/seg.c | 197 +++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 206 insertions(+) diff --git a/stand/kboot/Makefile b/stand/kboot/Makefile index 35d71cb064fc..cc972bc06ae3 100644 --- a/stand/kboot/Makefile +++ b/stand/kboot/Makefile @@ -30,6 +30,7 @@ SRCS= \ init.c \ kbootfdt.c \ main.c \ + seg.c \ termios.c \ util.c \ vers.c diff --git a/stand/kboot/kboot.h b/stand/kboot/kboot.h index c50f3f7d53a1..2d89933b51aa 100644 --- a/stand/kboot/kboot.h +++ b/stand/kboot/kboot.h @@ -35,6 +35,14 @@ const char *hostdisk_gen_probe(void); void hostdisk_zfs_probe(void); bool hostdisk_zfs_find_default(void); +/* seg.c */ +void init_avail(void); +void need_avail(int n); +void add_avail(uint64_t start, uint64_t end, uint64_t type); +void remove_avail(uint64_t start, uint64_t end, uint64_t type); +uint64_t first_avail(uint64_t align, uint64_t min_size, uint64_t type); +void print_avail(void); + /* util.c */ bool file2str(const char *fn, char *buffer, size_t buflen); bool file2u64(const char *fn, uint64_t *val); diff --git a/stand/kboot/seg.c b/stand/kboot/seg.c new file mode 100644 index 000000000000..41ded9b4083c --- /dev/null +++ b/stand/kboot/seg.c @@ -0,0 +1,197 @@ +/*- + * Copyright (c) 2023, Netflix, Inc. + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#include "stand.h" +#include "kboot.h" + +#include + +static struct memory_segments *segs; +static int nr_seg = 0; +static int segalloc = 0; + +void +init_avail(void) +{ + if (segs) + free(segs); + nr_seg = 0; + segalloc = 16; + segs = malloc(sizeof(*segs) * segalloc); + if (segs == NULL) + panic("not enough memory to get memory map\n"); +} + +/* + * Make sure at least n items can be accessed in the segs array. Note the + * realloc here will invalidate cached pointers (potentially), so addresses + * into the segs array must be recomputed after this call. + */ +void +need_avail(int n) +{ + if (n <= segalloc) + return; + + while (n > segalloc) + segalloc *= 2; + segs = realloc(segs, segalloc * sizeof(*segs)); + if (segs == NULL) + panic("not enough memory to get memory map\n"); +} + +/* + * Always called for a new range, so always just append a range, + * unless it's continuous with the prior range. + */ +void +add_avail(uint64_t start, uint64_t end, uint64_t type) +{ + /* + * This range is contiguous with the previous range, and is + * the same type: we can collapse the two. + */ + if (nr_seg >= 1 && + segs[nr_seg - 1].end + 1 == start && + segs[nr_seg - 1].type == type) { + segs[nr_seg - 1].end = end; + return; + } + + /* + * Otherwise we need to add a new range at the end, but don't need to + * adjust the current end. + */ + need_avail(nr_seg + 1); + segs[nr_seg].start = start; + segs[nr_seg].end = end; + segs[nr_seg].type = type; + nr_seg++; +} + +/* + * All or part of a prior entry needs to be modified. Given the structure of the + * code, we know that it will always be modifying the last time and/or extending + * the one before it if its contiguous. + */ +void +remove_avail(uint64_t start, uint64_t end, uint64_t type) +{ + struct memory_segments *s; + + /* + * simple case: we are extending a previously removed item. + */ + if (nr_seg >= 2) { + s = &segs[nr_seg - 2]; + if (s->end + 1 == start && + s->type == type) { + s->end = end; + /* Now adjust the ending element */ + s++; + if (s->end == end) { + /* we've used up the 'free' space */ + nr_seg--; + return; + } + /* Otherwise adjust the 'free' space */ + s->start = end + 1; + return; + } + } + + /* + * OK, we have four cases: + * (1) The new chunk is at the start of the free space, but didn't catch the above + * folding for whatever reason (different type, start of space). In this case, + * we allocate 1 additional item. The current end is copied to the new end. The + * current end is set to and the new end's start is set to end + 1. + * (2) The new chunk is in the middle of the free space. In this case we allocate 2 + * additional items. We copy the current end to the new end, set the new end's start + * to end + 1, the old end's end to start - 1 and the new item is + * (3) The new chunk is at the end of the current end. In this case we allocate 1 more + * and adjust the current end's end to start - 1 and set the new end to . + * (4) The new chunk is exactly the current end, except for type. In this case, we just adjust + * the type. + * We can assume we always have at least one chunk since that's created with new_avail() above + * necessarily before we are called to subset it. + */ + s = &segs[nr_seg - 1]; + if (s->start == start) { + if (s->end == end) { /* (4) */ + s->type = type; + return; + } + /* chunk at start of old chunk -> (1) */ + need_avail(nr_seg + 1); + s = &segs[nr_seg - 1]; /* Realloc may change pointers */ + s[1] = s[0]; + s->start = start; + s->end = end; + s->type = type; + s[1].start = end + 1; + nr_seg++; + return; + } + if (s->end == end) { /* At end of old chunk (3) */ + need_avail(nr_seg + 1); + s = &segs[nr_seg - 1]; /* Realloc may change pointers */ + s[1] = s[0]; + s->end = start - 1; + s[1].start = start; + s[1].type = type; + nr_seg++; + return; + } + /* In the middle, need to split things up (2) */ + need_avail(nr_seg + 2); + s = &segs[nr_seg - 1]; /* Realloc may change pointers */ + s[2] = s[1] = s[0]; + s->end = start - 1; + s[1].start = start; + s[1].end = end; + s[1].type = type; + s[2].start = end + 1; + nr_seg += 2; +} + +void +print_avail(void) +{ + printf("Found %d RAM segments:\n", nr_seg); + + for (int i = 0; i < nr_seg; i++) { + printf("%#jx-%#jx type %lu\n", + (uintmax_t)segs[i].start, + (uintmax_t)segs[i].end, + (u_long)segs[i].type); + } +} + +uint64_t +first_avail(uint64_t align, uint64_t min_size, uint64_t memtype) +{ + uint64_t s, len; + + for (int i = 0; i < nr_seg; i++) { + if (segs[i].type != memtype) /* Not candidate */ + continue; + s = roundup(segs[i].start, align); + if (s >= segs[i].end) /* roundup past end */ + continue; + len = segs[i].end - s + 1; + if (len >= min_size) { + printf("Found a big enough hole at in seg %d at %#jx (%#jx-%#jx)\n", + i, + (uintmax_t)s, + (uintmax_t)segs[i].start, + (uintmax_t)segs[i].end); + return (s); + } + } + + return (0); +}