From nobody Mon Jun 5 08:36:07 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 4QZRlW5YHnz4bM1s; Mon, 5 Jun 2023 08:36:07 +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 4QZRlW3F2Gz3xCj; Mon, 5 Jun 2023 08:36:07 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1685954167; 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=n7PPf5hn96BriOW9E6XJZxbIsJoaAJQ4m1GqMlNnnOM=; b=GOwbe8WqPYutkLP41HOsqVJv3rbjYwgZPMeM0M99IncgtTukZmDlA5eGcMNSMkPuc2nQl5 /eh8Ks6Up2lQNw1rdJWsQx7fsRD+6U33Y7VFR/xaSCziou7rIzGrRn6X8s+Dy58Mw/q3C6 ubKtK9h4ltUWu5aSkDc5Yhem1Pb3rWwqPC4NaifUlgSNhT/1EiOykt0RTMoX2VUD8/yD9G ZMpkYXb0uW3U1oeF1hItQtk/qZUh9Ayr6OPNhz9JcSAaRR4/z7PTR8F/9T+QsvYakiofwf IQcE1WNXctMJ/j8ajMgqoo2e0KxA7db2Q1Efg2rIwBR+qYeNTt9WbcMA/4Hxgw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1685954167; 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=n7PPf5hn96BriOW9E6XJZxbIsJoaAJQ4m1GqMlNnnOM=; b=yzdMh40JwacOki3hIfQQ9dHnq9KFgk/J/zV/RuaQOOT0gYAkWdnbGrlBJbc13DJWcQrEaX al/9l1hucLI7dR2pxQos7sE5bNUfOT3eWf/Od1+OAPoGDNJmx77clAdnBhX6Xd02yk6eLO owtRoMlfziBgl6wnjIFfA+6j1B5kTygMIrlw/0eh7A1rD3gd8NVc0Rnf54PFns9aEgXL4/ 29PTzCa5QtBaDNf8+PCHXWkHUvcb9tE4SBZ+ApmDB9QP608QPt/HTR/j9ezUA26dk4OewK GVtrfjCVi1aLLzEvZMhGGnbkbcXiy7H5lOFl6l2TfhCmg7922YGnjvIzv1dD4Q== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1685954167; a=rsa-sha256; cv=none; b=ZRX0rTxj1FhbmWDTkloMzNiiT74fjPmzHG5d4v+awJl3I4mcLeOnN9C21CUMcDHlXkpE1b pQwnMhS8SCY8DA3t/4l9dyFcL/G87DHKP84tmY4uF66jn8P6Aw9rORNT5Iq0vOCU8AxRXG IvpZZ/6c9xeykpVC5urOc7uRSK8xQqxXi2SzG2DHfVwrp5noqCO0AHciV54xcpcGjzHY7+ 03VCk5kwBcOEnAu/0PUmetx/pZoEfYNweQfw6luzCno4FshZdWaFNhyivb/LFyTUWAvVpY Bh5H0lWF033LCmxRKsGiCVti10CF6WIVGuXH2Bg8g6DyhHvCeH3R1kIq6msWlw== 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 4QZRlW2Ltgzgs5; Mon, 5 Jun 2023 08:36:07 +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 3558a72q024455; Mon, 5 Jun 2023 08:36:07 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 3558a7o7024454; Mon, 5 Jun 2023 08:36:07 GMT (envelope-from git) Date: Mon, 5 Jun 2023 08:36:07 GMT Message-Id: <202306050836.3558a7o7024454@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Konstantin Belousov Subject: git: c0360504add5 - stable/13 - unr(9): add iterator interface 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: kib X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: c0360504add56d422bb8f77ec7f7a32689a2e8b1 Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by kib: URL: https://cgit.FreeBSD.org/src/commit/?id=c0360504add56d422bb8f77ec7f7a32689a2e8b1 commit c0360504add56d422bb8f77ec7f7a32689a2e8b1 Author: Konstantin Belousov AuthorDate: 2023-05-12 22:49:29 +0000 Commit: Konstantin Belousov CommitDate: 2023-06-05 08:35:01 +0000 unr(9): add iterator interface (cherry picked from commit a014e0a3987a277a0e56c7fa5b9d895f735a8d1e) --- sys/kern/subr_unit.c | 121 +++++++++++++++++++++++++++++++++++++++++++++++++++ sys/sys/systm.h | 3 ++ 2 files changed, 124 insertions(+) diff --git a/sys/kern/subr_unit.c b/sys/kern/subr_unit.c index 0f4d25257553..ee67e5db01d6 100644 --- a/sys/kern/subr_unit.c +++ b/sys/kern/subr_unit.c @@ -238,6 +238,122 @@ ub_full(struct unrb *ub, int len) return (first_clear == -1); } +/* + * start: ipos = -1, upos = NULL; + * end: ipos = -1, upos = uh + */ +struct unrhdr_iter { + struct unrhdr *uh; + int ipos; + int upos_first_item; + void *upos; +}; + +void * +create_iter_unr(struct unrhdr *uh) +{ + struct unrhdr_iter *iter; + + iter = Malloc(sizeof(*iter)); + iter->ipos = -1; + iter->uh = uh; + iter->upos = NULL; + iter->upos_first_item = -1; + return (iter); +} + +static void +next_iter_unrl(struct unrhdr *uh, struct unrhdr_iter *iter) +{ + struct unr *up; + struct unrb *ub; + u_int y; + int c; + + if (iter->ipos == -1) { + if (iter->upos == uh) + return; + y = uh->low - 1; + if (uh->first == 0) { + up = TAILQ_FIRST(&uh->head); + if (up == NULL) { + iter->upos = uh; + return; + } + iter->upos = up; + if (up->ptr == NULL) + iter->upos = NULL; + else + iter->upos_first_item = uh->low; + } + } else { + y = iter->ipos; + } + + up = iter->upos; + + /* Special case for the compacted [low, first) run. */ + if (up == NULL) { + if (y + 1 < uh->low + uh->first) { + iter->ipos = y + 1; + return; + } + up = iter->upos = TAILQ_FIRST(&uh->head); + iter->upos_first_item = uh->low + uh->first; + } + + for (;;) { + if (y + 1 < iter->upos_first_item + up->len) { + if (up->ptr == uh) { + iter->ipos = y + 1; + return; + } else if (is_bitmap(uh, up)) { + ub = up->ptr; + bit_ffs_at(&ub->map[0], + y + 1 - iter->upos_first_item, + up->len, &c); + if (c != -1) { + iter->ipos = iter->upos_first_item + c; + return; + } + } + } + iter->upos_first_item += up->len; + y = iter->upos_first_item - 1; + up = iter->upos = TAILQ_NEXT((struct unr *)iter->upos, list); + if (iter->upos == NULL) { + iter->ipos = -1; + iter->upos = uh; + return; + } + } +} + +/* + * returns -1 on end, otherwise the next element + */ +int +next_iter_unr(void *handle) +{ + struct unrhdr *uh; + struct unrhdr_iter *iter; + + iter = handle; + uh = iter->uh; + if (uh->mtx != NULL) + mtx_lock(uh->mtx); + next_iter_unrl(uh, iter); + if (uh->mtx != NULL) + mtx_unlock(uh->mtx); + return (iter->ipos); +} + +void +free_iter_unr(void *handle) +{ + Free(handle); +} + #if defined(DIAGNOSTIC) || !defined(_KERNEL) /* * Consistency check function. @@ -1056,6 +1172,11 @@ test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[]) } } +static void +test_iter(void) +{ +} + static void usage(char **argv) { diff --git a/sys/sys/systm.h b/sys/sys/systm.h index 828297e5b948..4b479e95aa2f 100644 --- a/sys/sys/systm.h +++ b/sys/sys/systm.h @@ -483,6 +483,9 @@ int alloc_unr(struct unrhdr *uh); int alloc_unr_specific(struct unrhdr *uh, u_int item); int alloc_unrl(struct unrhdr *uh); void free_unr(struct unrhdr *uh, u_int item); +void *create_iter_unr(struct unrhdr *uh); +int next_iter_unr(void *handle); +void free_iter_unr(void *handle); #ifndef __LP64__ #define UNR64_LOCKED