From patchwork Thu Feb 3 08:22:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: MRoeder@metz-connect.com X-Patchwork-Id: 1587919 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=lists.infradead.org header.i=@lists.infradead.org header.a=rsa-sha256 header.s=bombadil.20210309 header.b=LfPhlp3E; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=none (no SPF record) smtp.mailfrom=lists.openwrt.org (client-ip=2607:7c80:54:e::133; helo=bombadil.infradead.org; envelope-from=openwrt-devel-bounces+incoming=patchwork.ozlabs.org@lists.openwrt.org; receiver=) Received: from bombadil.infradead.org (bombadil.infradead.org [IPv6:2607:7c80:54:e::133]) (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) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4JqBks0Z5vz9s8s for ; Thu, 3 Feb 2022 19:33:09 +1100 (AEDT) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-Id:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=6TnxFEkj9fqh0gZ87naChMk3iHH40BkFGXPPkQfg3k8=; b=LfPhlp3EkQDyhj 4WuLoSNz9SjeCn2sGxadzWcvg7540jhM4Ao62qIHTq5p/eGmv3ZWxQqWh60pKE+9/Iglx4TnnGCz4 V5Cq6yNew1TogXzroVlXPVCnRnTaOwc/tyMBNJJHnQpdQyEw6T40yMq7vXByV0OOtKGYtNVkyIO2L z/JyA/psXtMEhZuuQ7GuFuuWyuwYMwN56y8OBeWhIlXp1FYCatqJLaF/ims0VS+/8nFAw1bipWDYx WFJveDR7HgifYvx+Un67gxqbLeNHPFzv8s+W+JrmVCAkjT7G0YeMjaw0yrXcBeN9O1ns1LG3g5uK5 ZIzqP+RCRWXAkYPUkqYA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1nFXW8-000Mih-D8; Thu, 03 Feb 2022 08:31:01 +0000 Received: from mail.ria-btr.de ([217.7.162.42]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1nFXOR-000JRi-Dv for openwrt-devel@lists.openwrt.org; Thu, 03 Feb 2022 08:23:05 +0000 Received: from svadsw102.metzconnect.local ( [10.10.0.1]) by mail.ria-btr.de (Reddoxx engine) with SMTP id 7E30C51CC41; Thu, 3 Feb 2022 09:22:51 +0100 Received: from debian-vm.metzconnect.local ([10.10.6.102]) by svadsw102.metzconnect.local (IBM Domino Release 9.0.1FP5) with ESMTP id 2022020309225086-1206388 ; Thu, 3 Feb 2022 09:22:50 +0100 From: mroeder@metz-connect.com To: openwrt-devel@lists.openwrt.org Cc: John Crispin , =?utf-8?q?Martin_R=C3=B6der?= Subject: [PATCH 1/1] cache: fix AVL tree traversal in cache_record_find() and cache_host_is_known() Date: Thu, 3 Feb 2022 09:22:30 +0100 Message-Id: <20220203082230.57497-2-mroeder@metz-connect.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20220203082230.57497-1-mroeder@metz-connect.com> References: <20220203082230.57497-1-mroeder@metz-connect.com> MIME-Version: 1.0 X-MIMETrack: Itemize by SMTP Server on SVDOMW101/FAM(Release 9.0.1FP5|November 22, 2015) at 03.02.2022 09:22:50, Serialize by Router on SVDOMW101/FAM(Release 9.0.1FP5|November 22, 2015) at 03.02.2022 09:22:51 X-TNEFEvaluated: 1 X-EsetResult: clean, is OK X-EsetId: 37303A2985AF0E52667D61 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20220203_002303_822127_4158E057 X-CRM114-Status: UNSURE ( 8.90 ) X-CRM114-Notice: Please train this message. X-Spam-Score: -0.0 (/) X-Spam-Report: =?unknown-8bit?q?Spam_detection_software=2C_running_on_the_sy?= =?unknown-8bit?q?stem_=22bombadil=2Einfradead=2Eorg=22=2C?= =?unknown-8bit?q?_has_NOT_identified_this_incoming_email_as_spam=2E__The_ori?= =?unknown-8bit?q?ginal?= =?unknown-8bit?q?_message_has_been_attached_to_this_so_you_can_view_it_or_la?= =?unknown-8bit?q?bel?= =?unknown-8bit?q?_similar_future_email=2E__If_you_have_any_questions=2C_see?= =?unknown-8bit?q?_the_administrator_of_that_system_for_details=2E?= =?unknown-8bit?q?_?= =?unknown-8bit?q?_Content_preview=3A__From=3A_Martin_R=C3=B6der_=3Cmroeder?= =?unknown-8bit?q?=40metz-connect=2Ecom=3E_The_AVL_tree?= =?unknown-8bit?q?_traversal_in_both_functions_systematically_misses_the_last?= =?unknown-8bit?q?_AVL_tree_element=2E?= =?unknown-8bit?q?_This_can_lead_to_duplicate_cache_entries_and_lookup_failur?= =?unknown-8bit?q?es=2E_The_fix_duplicates?= =?unknown-8bit?q?_the_correct_AVL_tree_traversal_approach_of_cache=5Fdump=5F?= =?unknown-8bit?q?recursive=28=29=2E_?= =?unknown-8bit?q?_?= =?unknown-8bit?q?_Content_analysis_details=3A___=28-0=2E0_points=2C_5=2E0_re?= =?unknown-8bit?q?quired=29?= =?unknown-8bit?q?_?= =?unknown-8bit?q?_pts_rule_name______________description?= =?unknown-8bit?q?_----_----------------------_------------------------------?= =?unknown-8bit?q?--------------------?= =?unknown-8bit?q?_-0=2E0_SPF=5FPASS_______________SPF=3A_sender_matches_SPF_?= =?unknown-8bit?q?record?= =?unknown-8bit?q?_-0=2E0_SPF=5FHELO=5FPASS__________SPF=3A_HELO_matches_SPF_?= =?unknown-8bit?q?record?= X-BeenThere: openwrt-devel@lists.openwrt.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: OpenWrt Development List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "openwrt-devel" Errors-To: openwrt-devel-bounces+incoming=patchwork.ozlabs.org@lists.openwrt.org From: Martin Röder The AVL tree traversal in both functions systematically misses the last AVL tree element. This can lead to duplicate cache entries and lookup failures. The fix duplicates the correct AVL tree traversal approach of cache_dump_recursive(). Signed-off-by: Martin Röder --- cache.c | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-) diff --git a/cache.c b/cache.c index ea6a4c8..d1816df 100644 --- a/cache.c +++ b/cache.c @@ -191,13 +191,10 @@ cache_record_find(char *record, int type, int port, int rdlength, uint8_t *rdata { struct cache_record *l = avl_find_element(&records, record, l, avl); - if (!l) - return NULL; - - while (l && !avl_is_last(&records, &l->avl) && !strcmp(l->record, record)) { + while (l && !strcmp(l->record, record)) { struct cache_record *r = l; - l = avl_next_element(l, avl); + l = !avl_is_last(&records, &l->avl) ? avl_next_element(l, avl) : NULL; if (r->type != type) continue; @@ -227,13 +224,10 @@ cache_host_is_known(char *record) { struct cache_record *l = avl_find_element(&records, record, l, avl); - if (!l) - return 0; - - while (l && !avl_is_last(&records, &l->avl) && !strcmp(l->record, record)) { + while (l && !strcmp(l->record, record)) { struct cache_record *r = l; - l = avl_next_element(l, avl); + l = !avl_is_last(&records, &l->avl) ? avl_next_element(l, avl) : NULL; if ((r->type != TYPE_A) && (r->type != TYPE_AAAA)) continue; return 1;