From nobody Mon May 29 22:11:23 2023 X-Original-To: dev-commits-src-main@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 4QVV9S0v1Xz4XFj2; Mon, 29 May 2023 22:11:24 +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 4QVV9S0QS4z3K8S; Mon, 29 May 2023 22:11:24 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1685398284; 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=cyQXl9LWUYipc5WTyCHwIUB62P3uopSzi3bXYUYQnms=; b=OFoWdA2nQQInIAfq74qYC0TLuIeTTxeUTN0UKwb9eMiKJ5FsEV4BWmAgsZB0gzHC2bhGC2 s/I+yojDWbQ0q/rK8FCoqG71znzwqITqmGrqr6lNbgM6Y3S9t/H9O/R2hRFHY8loEQTEYi lCkM0Qnvc9Cvkl807/KmNBeETy4h23cqg/wSBNMC+FTXURsqHLCYSEWH/zfITVwQ4qpsfe /cFQ9REZqxM6BHIHm27bCZEIiEdGvN7jIQ8kqZdGV87QStPqcA0JC1JB20TynUFpR2WsEz RoT9g31C5iAUaNOGuXgKb9GOnxfyu+kfrWuDrvi68m7aCKlJyNOAGN3BEVS+hg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1685398284; 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=cyQXl9LWUYipc5WTyCHwIUB62P3uopSzi3bXYUYQnms=; b=RklPGesaRv7zxg7i9p3oiXOw2wG9K/eDitmMqdOYaHM004iu6/bxjmR353f9qhX9iv6gBm 42QU8CaJ+OnM9aco/0bCU5hT6h+eIcYT6hcOITkTq5ik9Xys13vznXD7WxnrDoLB3kQDxa z80/DL4kdp275F41YPzQVQF06w+K3zay8k7iLMPK6HmBg7oL9TCSA1JKDbheCZ6eNhn23U oKwWz6Y9yJOa9TI/f98CCpK+60XWuXFk2A6gLByXBAtR3NqkogwmRMrHYij1/QakW3JSWo Jz7Q1fuaUtTGT+kDWJaUmmKL8nnsdTKusKg+k2iMaixowY57aeqmf5EoYuCeGA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1685398284; a=rsa-sha256; cv=none; b=L3dApxdDuyHhSG6A1dymejPkMGgNMNEMUlFOgnS3RAaXm7sDJz/0ITPyY6LEAHTWWlIKKk KprHXG8CLplhIsxIwIzj/6TzKTVOY4vZbR3S9BQJNIJliHTc2CftHFYTw4cmBMlHCoV6Ss f/oS5f1w+Ef0MbeHo9AhxV3tFAUSsH2nItIPpMIF9BT21XWIg5MwoOWDbeT0HMH6xOuaTI 6Agb9ZCwiAA0JW39Pl7MhREHe6nblzgDkEiCg1VPDqKNLCqKzTT7wnhoMMe4zGNH5UcN5t q5YOyB4RBtcMfiDxQTIACF6rLouQv1gS16q7DJPhOK0vCVRZryyvImE2D6HRFg== 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 4QVV9R6WymzSkK; Mon, 29 May 2023 22:11:23 +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 34TMBNEi044773; Mon, 29 May 2023 22:11:23 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 34TMBNjE044772; Mon, 29 May 2023 22:11:23 GMT (envelope-from git) Date: Mon, 29 May 2023 22:11:23 GMT Message-Id: <202305292211.34TMBNjE044772@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Konstantin Belousov Subject: git: a014e0a3987a - main - unr(9): add iterator interface List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@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/main X-Git-Reftype: branch X-Git-Commit: a014e0a3987a277a0e56c7fa5b9d895f735a8d1e Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by kib: URL: https://cgit.FreeBSD.org/src/commit/?id=a014e0a3987a277a0e56c7fa5b9d895f735a8d1e commit a014e0a3987a277a0e56c7fa5b9d895f735a8d1e Author: Konstantin Belousov AuthorDate: 2023-05-12 22:49:29 +0000 Commit: Konstantin Belousov CommitDate: 2023-05-29 22:10:36 +0000 unr(9): add iterator interface Reviewed by: markj Tested by: pho Sponsored by: The FreeBSD Foundation MFC after: 1 week Differential revision: https://reviews.freebsd.org/D40089 --- 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 0b8be66a8c4d..01bd23a1a2c4 100644 --- a/sys/kern/subr_unit.c +++ b/sys/kern/subr_unit.c @@ -225,6 +225,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. @@ -1043,6 +1159,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 333a72ba9e30..7099c484dcee 100644 --- a/sys/sys/systm.h +++ b/sys/sys/systm.h @@ -509,6 +509,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); struct unrhdr64 { uint64_t counter;