From patchwork Fri Jan 13 21:51:51 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mark Michelson X-Patchwork-Id: 1726409 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=2605:bc80:3010::136; helo=smtp3.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=hWoEFI6e; dkim-atps=neutral Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Ntw9v0LvTz23fd for ; Sat, 14 Jan 2023 08:52:02 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 965EF6114D; Fri, 13 Jan 2023 21:52:00 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 965EF6114D Authentication-Results: smtp3.osuosl.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=hWoEFI6e X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HIq8RuCk-cZL; Fri, 13 Jan 2023 21:51:59 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp3.osuosl.org (Postfix) with ESMTPS id 79FED60ADC; Fri, 13 Jan 2023 21:51:58 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 79FED60ADC Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 2FB5EC0032; Fri, 13 Jan 2023 21:51:58 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 40563C002D for ; Fri, 13 Jan 2023 21:51:57 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 15ABD40123 for ; Fri, 13 Jan 2023 21:51:57 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 15ABD40123 Authentication-Results: smtp2.osuosl.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=hWoEFI6e X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id cpjfCI4bZrTo for ; Fri, 13 Jan 2023 21:51:56 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 40CB8400C8 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by smtp2.osuosl.org (Postfix) with ESMTPS id 40CB8400C8 for ; Fri, 13 Jan 2023 21:51:56 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1673646714; 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=7pbQzvA9y+7+KJ8rM0A+K9gwtemRL++w2Ugjckm+Lec=; b=hWoEFI6ecGLdOhqD2zdRGJq7JfG/zS4eC1EIf2gcPbtagUxRCU4GDwWEJxP3NYnCm/jwaf IxFMvBrohdxnKtnBoWkUccINi2jg7B1vAIhOOfc0mi440DoUbEYTexjkUOawa0K4DA/Xc8 8PdtVJD84ZMOR9qmsP+pGnQW3tQGgRA= Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-548-INIABGoCNLCBXvcAiz6QtA-1; Fri, 13 Jan 2023 16:51:53 -0500 X-MC-Unique: INIABGoCNLCBXvcAiz6QtA-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 6921A3C0D194 for ; Fri, 13 Jan 2023 21:51:53 +0000 (UTC) Received: from localhost.localdomain.com (unknown [10.22.48.13]) by smtp.corp.redhat.com (Postfix) with ESMTP id 00D942026D68 for ; Fri, 13 Jan 2023 21:51:52 +0000 (UTC) From: Mark Michelson To: dev@openvswitch.org Date: Fri, 13 Jan 2023 16:51:51 -0500 Message-Id: <20230113215151.106211-1-mmichels@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Subject: [ovs-dev] [PATCH] id-pool: Refactor to use a bitmap. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Using a bitmap makes the id-pool use less memory and be more cache-friendly. It theoretically should be faster since hashes do not have to be computed. This takes the approach of expanding the bitmap when necessary rather than allocating the entire space at once. This makes the approach less memory-intensive for id pools with a large theoretical maximum number of values. Signed-off-by: Mark Michelson --- lib/id-pool.c | 110 +++++++++++++++++++++----------------------------- 1 file changed, 45 insertions(+), 65 deletions(-) diff --git a/lib/id-pool.c b/lib/id-pool.c index 69910ad08..68150b193 100644 --- a/lib/id-pool.c +++ b/lib/id-pool.c @@ -17,25 +17,20 @@ #include #include "id-pool.h" -#include "openvswitch/hmap.h" -#include "hash.h" +#include "bitmap.h" -struct id_node { - struct hmap_node node; - uint32_t id; -}; +#define ID_POOL_BASE_ALLOC 64 struct id_pool { - struct hmap map; + unsigned long *bitmap; + uint32_t bitmap_size; /* Current highest offset the bitmap can hold */ uint32_t base; /* IDs in the range of [base, base + n_ids). */ uint32_t n_ids; /* Total number of ids in the pool. */ - uint32_t next_free_id; /* Possible next free id. */ }; static void id_pool_init(struct id_pool *pool, uint32_t base, uint32_t n_ids); static void id_pool_uninit(struct id_pool *pool); -static struct id_node *id_pool_find(struct id_pool *pool, uint32_t id); struct id_pool * id_pool_create(uint32_t base, uint32_t n_ids) @@ -62,96 +57,81 @@ id_pool_init(struct id_pool *pool, uint32_t base, uint32_t n_ids) { pool->base = base; pool->n_ids = n_ids; - pool->next_free_id = base; - hmap_init(&pool->map); + pool->bitmap_size = MIN(n_ids, ID_POOL_BASE_ALLOC); + pool->bitmap = bitmap_allocate(pool->bitmap_size); } static void id_pool_uninit(struct id_pool *pool) { - struct id_node *id_node; + free(pool->bitmap); + pool->bitmap = NULL; +} - HMAP_FOR_EACH_POP(id_node, node, &pool->map) { - free(id_node); +static bool +id_pool_expand(struct id_pool *pool, uint32_t target) +{ + if (target >= pool->n_ids) { + return false; } - hmap_destroy(&pool->map); + uint32_t new_bitmap_size = MAX(pool->bitmap_size * 2, target); + new_bitmap_size = MAX(new_bitmap_size, pool->n_ids); + unsigned long *new_bitmap = bitmap_allocate(new_bitmap_size); + + memcpy(new_bitmap, pool->bitmap, bitmap_n_bytes(pool->bitmap_size)); + + id_pool_uninit(pool); + pool->bitmap = new_bitmap; + pool->bitmap_size = new_bitmap_size; + return true; } -static struct id_node * -id_pool_find(struct id_pool *pool, uint32_t id) +static bool +id_pool_add__(struct id_pool *pool, uint32_t offset) { - size_t hash; - struct id_node *id_node; - - hash = hash_int(id, 0); - HMAP_FOR_EACH_WITH_HASH(id_node, node, hash, &pool->map) { - if (id == id_node->id) { - return id_node; - } + if (offset >= pool->n_ids) { + return false; + } + + if (offset >= pool->bitmap_size && !id_pool_expand(pool, offset)) { + return false; } - return NULL; + + bitmap_set1(pool->bitmap, offset); + return true; } void id_pool_add(struct id_pool *pool, uint32_t id) { - struct id_node *id_node = xmalloc(sizeof *id_node); - size_t hash; + if (id < pool->base) { + return; + } - id_node->id = id; - hash = hash_int(id, 0); - hmap_insert(&pool->map, &id_node->node, hash); + id_pool_add__(pool, id - pool->base); } bool id_pool_alloc_id(struct id_pool *pool, uint32_t *id_) { - uint32_t id; + size_t offset; if (pool->n_ids == 0) { return false; } - if (!(id_pool_find(pool, pool->next_free_id))) { - id = pool->next_free_id; - goto found_free_id; - } - - for(id = pool->base; id < pool->base + pool->n_ids; id++) { - if (!id_pool_find(pool, id)) { - goto found_free_id; - } - } - - /* Not available. */ - return false; - -found_free_id: - id_pool_add(pool, id); - - if (id + 1 < pool->base + pool->n_ids) { - pool->next_free_id = id + 1; - } else { - pool->next_free_id = pool->base; + offset = bitmap_scan(pool->bitmap, 0, 0, pool->bitmap_size); + if (!id_pool_add__(pool, offset)) { + return false; } - *id_ = id; + *id_ = offset + pool->base; return true; } void id_pool_free_id(struct id_pool *pool, uint32_t id) { - struct id_node *id_node; - if (id >= pool->base && (id < pool->base + pool->n_ids)) { - id_node = id_pool_find(pool, id); - if (id_node) { - hmap_remove(&pool->map, &id_node->node); - if (id < pool->next_free_id) { - pool->next_free_id = id; - } - free(id_node); - } - } + bitmap_set0(pool->bitmap, id - pool->base); }