From nobody Thu Nov 28 13:57:47 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=quarantine dis=none) header.from=suse.com ARC-Seal: i=1; a=rsa-sha256; t=1670947320; cv=none; d=zohomail.com; s=zohoarc; b=ACN/eP0kLpoICijdTnOEmFDNTh+BISr0V+xsLGi3bhhUc9coCJcyOG0SuSXTACejQJfeEPO0raeDcMHoEXASMdyhQ3YAfdDBiDYbYWJnXcu3nre6e8HpIIglF22yh1+BqCL5TGf1gSxqygTaiskd3r7yfeUwgXSMw/BzLYGJUD4= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1670947320; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=1UptZp8ROkSilFG4tYMMbyMYYtc6wOlksuu4FVRkdJc=; b=fUH6aAjNEDFE5rZpG7UtR07qt0BDE4um8nEetWLV4zhER9rgVav+YfjzEjCV7/e6T2ePb+x6Qq/doorAjiyc2nWrXOeNR8qYees2H1Wpc7OBW7vALRdcsSztKz0NHhbX2aPl4qdVqxwpc8gdlg27199yiCp/8rF/ecaCx3lrxLE= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=quarantine dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1670947320930554.0526680835361; Tue, 13 Dec 2022 08:02:00 -0800 (PST) Received: from list by lists.xenproject.org with outflank-mailman.460738.718737 (Exim 4.92) (envelope-from ) id 1p57iY-0003PT-4F; Tue, 13 Dec 2022 16:01:18 +0000 Received: by outflank-mailman (output) from mailman id 460738.718737; Tue, 13 Dec 2022 16:01:18 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1p57iX-0003PK-Vc; Tue, 13 Dec 2022 16:01:17 +0000 Received: by outflank-mailman (input) for mailman id 460738; Tue, 13 Dec 2022 16:01:17 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1p57iX-0001ta-2t for xen-devel@lists.xenproject.org; Tue, 13 Dec 2022 16:01:17 +0000 Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 5fb2cfc3-7aff-11ed-8fd2-01056ac49cbb; Tue, 13 Dec 2022 17:01:16 +0100 (CET) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id CCB881FDAB; Tue, 13 Dec 2022 16:01:15 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 9B29F138EE; Tue, 13 Dec 2022 16:01:15 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id fUujJMuhmGOqKQAAMHmgww (envelope-from ); Tue, 13 Dec 2022 16:01:15 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 5fb2cfc3-7aff-11ed-8fd2-01056ac49cbb DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=susede1; t=1670947275; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=1UptZp8ROkSilFG4tYMMbyMYYtc6wOlksuu4FVRkdJc=; b=S3zy+L0C34e7+ma26sn5nOxhXTJO8ZBhTTchLaa7GCfFstMmofecEK6w6uo81hxD7NiLDM lBpEy5/OatcKh7znQwn4NWgELqX4t2qZ9xKwK/7kXw6+tNHM6J/Z8jpCsyzsGPkTxLkcq5 KxVN/JbwlNgBXSwnDuKj6B1dYDQBpsU= From: Juergen Gross To: xen-devel@lists.xenproject.org Cc: Juergen Gross , Wei Liu , Julien Grall , Anthony PERARD , Julien Grall Subject: [PATCH v2 05/19] tools/xenstore: enhance hashtable implementation Date: Tue, 13 Dec 2022 17:00:31 +0100 Message-Id: <20221213160045.28170-6-jgross@suse.com> X-Mailer: git-send-email 2.35.3 In-Reply-To: <20221213160045.28170-1-jgross@suse.com> References: <20221213160045.28170-1-jgross@suse.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @suse.com) X-ZM-MESSAGEID: 1670947321616100001 Content-Type: text/plain; charset="utf-8" Today it is possible to set a flag when calling hashtable_destroy() in order to specify whether the data associated with the hashtable entries should be freed or not. The keys of the entries will always be freed. Change that by replacing the flag of hashtable_destroy() by two flags for create_hashtable() which will specify whether the data and/or the key of each entry should be freed or not. This will enable users to have the key e.g. as part of the data. Add a new function hashtable_iterate() to call a user specified function for each entry in the hashtable. Add new primes to the primetable in order to support smaller sizes of the hashtable. The primes are selected according to: https://planetmath.org/goodhashtableprimes Update the URL in the source as the old one wasn't correct any longer. Signed-off-by: Juergen Gross Reviewed-by: Julien Grall --- V2: - add const to hashtable_iterate() callback (Julien Grall) --- tools/xenstore/hashtable.c | 66 +++++++++++++++++++++++---------- tools/xenstore/hashtable.h | 35 +++++++++++++++-- tools/xenstore/xenstored_core.c | 7 ++-- 3 files changed, 82 insertions(+), 26 deletions(-) diff --git a/tools/xenstore/hashtable.c b/tools/xenstore/hashtable.c index 6ac336eff1..299549c51e 100644 --- a/tools/xenstore/hashtable.c +++ b/tools/xenstore/hashtable.c @@ -16,6 +16,7 @@ struct entry =20 struct hashtable { unsigned int tablelength; + unsigned int flags; struct entry **table; unsigned int entrycount; unsigned int loadlimit; @@ -25,12 +26,11 @@ struct hashtable { }; =20 /* -Credit for primes table: Aaron Krowne - http://br.endernet.org/~akrowne/ - http://planetmath.org/encyclopedia/GoodHashTablePrimes.html -*/ + * Credit for primes table: Aaron Krowne + * https://planetmath.org/goodhashtableprimes + */ static const unsigned int primes[] =3D { -53, 97, 193, 389, +11, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, @@ -52,7 +52,8 @@ indexFor(unsigned int tablelength, unsigned int hashvalue= ) { struct hashtable * create_hashtable(unsigned int minsize, unsigned int (*hashf) (void*), - int (*eqf) (void*,void*)) + int (*eqf) (void*,void*), + unsigned int flags) { struct hashtable *h; unsigned int pindex, size =3D primes[0]; @@ -73,6 +74,7 @@ create_hashtable(unsigned int minsize, goto err1; =20 h->tablelength =3D size; + h->flags =3D flags; h->primeindex =3D pindex; h->entrycount =3D 0; h->hashfn =3D hashf; @@ -235,7 +237,8 @@ hashtable_remove(struct hashtable *h, void *k) *pE =3D e->next; h->entrycount--; v =3D e->v; - free(e->k); + if (h->flags & HASHTABLE_FREE_KEY) + free(e->k); free(e); return v; } @@ -246,29 +249,52 @@ hashtable_remove(struct hashtable *h, void *k) } =20 /*************************************************************************= ****/ -/* destroy */ -void -hashtable_destroy(struct hashtable *h, int free_values) +int +hashtable_iterate(struct hashtable *h, + int (*func)(const void *k, void *v, void *arg), void *ar= g) { + int ret; unsigned int i; struct entry *e, *f; struct entry **table =3D h->table; - if (free_values) + + for (i =3D 0; i < h->tablelength; i++) { - for (i =3D 0; i < h->tablelength; i++) + e =3D table[i]; + while (e) { - e =3D table[i]; - while (NULL !=3D e) - { f =3D e; e =3D e->next; free(f->k); free(f->v); free(f); } + f =3D e; + e =3D e->next; + ret =3D func(f->k, f->v, arg); + if (ret) + return ret; } } - else + + return 0; +} + +/*************************************************************************= ****/ +/* destroy */ +void +hashtable_destroy(struct hashtable *h) +{ + unsigned int i; + struct entry *e, *f; + struct entry **table =3D h->table; + + for (i =3D 0; i < h->tablelength; i++) { - for (i =3D 0; i < h->tablelength; i++) + e =3D table[i]; + while (NULL !=3D e) { - e =3D table[i]; - while (NULL !=3D e) - { f =3D e; e =3D e->next; free(f->k); free(f); } + f =3D e; + e =3D e->next; + if (h->flags & HASHTABLE_FREE_KEY) + free(f->k); + if (h->flags & HASHTABLE_FREE_VALUE) + free(f->v); + free(f); } } free(h->table); diff --git a/tools/xenstore/hashtable.h b/tools/xenstore/hashtable.h index 62fef6081a..6d65431f96 100644 --- a/tools/xenstore/hashtable.h +++ b/tools/xenstore/hashtable.h @@ -12,13 +12,21 @@ struct hashtable; * @param minsize minimum initial size of hashtable * @param hashfunction function for hashing keys * @param key_eq_fn function for determining key equality + * @param flags flags HASHTABLE_* * @return newly created hashtable or NULL on failure */ =20 +/* Let hashtable_destroy() free the entries' values. */ +#define HASHTABLE_FREE_VALUE (1U << 0) +/* Let hashtable_remove() and hashtable_destroy() free the entries' keys. = */ +#define HASHTABLE_FREE_KEY (1U << 1) + struct hashtable * create_hashtable(unsigned int minsize, unsigned int (*hashfunction) (void*), - int (*key_eq_fn) (void*,void*)); + int (*key_eq_fn) (void*,void*), + unsigned int flags +); =20 /*************************************************************************= **** * hashtable_insert @@ -76,16 +84,37 @@ hashtable_remove(struct hashtable *h, void *k); unsigned int hashtable_count(struct hashtable *h); =20 +/*************************************************************************= **** + * hashtable_iterate + + * @name hashtable_iterate + * @param h the hashtable + * @param func function to call for each entry + * @param arg user supplied parameter for func + * @return 0 if okay, non-zero return value of func (and iteration + * was aborted) + * + * Iterates over all entries in the hashtable and calls func with the + * key, value, and the user supplied parameter. + * func returning a non-zero value will abort the iteration. In case func = is + * removing an entry other than itself from the hashtable, it must return a + * non-zero value in order to abort the iteration. Inserting entries is + * allowed, but it is undefined whether func will be called for those new + * entries during this iteration. + */ +int +hashtable_iterate(struct hashtable *h, + int (*func)(const void *k, void *v, void *arg), void *ar= g); + /*************************************************************************= **** * hashtable_destroy =20 * @name hashtable_destroy * @param h the hashtable - * @param free_values whether to call 'free' on the remaining va= lues */ =20 void -hashtable_destroy(struct hashtable *h, int free_values); +hashtable_destroy(struct hashtable *h); =20 #endif /* __HASHTABLE_CWC22_H__ */ =20 diff --git a/tools/xenstore/xenstored_core.c b/tools/xenstore/xenstored_cor= e.c index 8c2cca62b7..1650821922 100644 --- a/tools/xenstore/xenstored_core.c +++ b/tools/xenstore/xenstored_core.c @@ -2512,7 +2512,9 @@ void check_store(void) .enoent =3D check_store_enoent, }; =20 - reachable =3D create_hashtable(16, hash_from_key_fn, keys_equal_fn); + /* Don't free values (they are all void *1) */ + reachable =3D create_hashtable(16, hash_from_key_fn, keys_equal_fn, + HASHTABLE_FREE_KEY); if (!reachable) { log("check_store: ENOMEM"); return; @@ -2526,8 +2528,7 @@ void check_store(void) clean_store(reachable); log("Checking store complete."); =20 - hashtable_destroy(reachable, 0 /* Don't free values (they are all - (void *)1) */); + hashtable_destroy(reachable); } =20 =20 --=20 2.35.3