From patchwork Sun Mar 31 06:41:29 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Brian Vazquez X-Patchwork-Id: 1071428 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="O2uPrXiB"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 44X5X60hgSz9sBb for ; Sun, 31 Mar 2019 17:43:18 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731367AbfCaGmG (ORCPT ); Sun, 31 Mar 2019 02:42:06 -0400 Received: from mail-pl1-f195.google.com ([209.85.214.195]:40325 "EHLO mail-pl1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731349AbfCaGmE (ORCPT ); Sun, 31 Mar 2019 02:42:04 -0400 Received: by mail-pl1-f195.google.com with SMTP id b11so2924040plr.7; Sat, 30 Mar 2019 23:42:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=TfiF5XnESs3rd2LTH3SlV6CzghcxJZ6+t1a6r0fB5X4=; b=O2uPrXiB40QJIQvIj0PMtJfoc4MWpLva8CplaNmebtV0G8XBt2p7inVFXNo1uQYoxH /PlebslAzd/Gy4uc8aleNnyPTCBImE8qc98Y3ejl0gKfN3tjN31DLfhfMdhUkhqrC2h7 w07oLdzgzCvXk78vUdQGRnRVd+gwJiQUaVItzJcKK8QDEUSBdbFw94XE+sxgFywamcpR JDWYqWcnCFYsIImJeHHp6cWJKTHdPaftrXO7XA+5rVOYbLD2f6EfcReW8JHH3YQ/Zdr3 Qqdy8DQlzj9HtNAuuEzyX+lK68OXiMHBrbVgZEmf8sHYAq1CtTPxpmIOacDi7+JkgRFj UQAg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=TfiF5XnESs3rd2LTH3SlV6CzghcxJZ6+t1a6r0fB5X4=; b=BWUU3R8Wxk30iB8Z4wbFmyDckzav7tUjl+8qIhfo6Rrj9+zuTlDBJwq9SR5i10Uxk7 lXze66NFc/JFLjlvUWRGGkfKHtCEs+cH2bDvxqdS2VDdpXLW5qTCqFlDvRm3fSylZxwB Nm9hBPw0CRASyOX+pJZl8vFFnPr5MSrP0T6d2h/I3sdp3qhKqSroS/5V6x4RMDgb4uZO SmUq4O72F51tFyy1S1nsxtznaNBYE5D4JIS9cM4m6ZV1fGzzeTLyZYBk9q//X44/1cOY tHyxTJpmXgVY4n3ybFESGZNK+iTYky3SaHw/XmXoc+z76RMbvRoCaPEHZHwZ8O45qE5d Vflw== X-Gm-Message-State: APjAAAVvVAAyc55RV6u42K+N9s1w4Azyem3vOw19IdGXqyijlFiCVQ5P zb6bA9hJpHotQ3BTsh3UjnQ= X-Google-Smtp-Source: APXvYqxV3xaU/1oEMCCoazXRAqjbwWbhVK3DGoK3LeIxDd5cl5lJRJwiXYjjf3jebPBbgUHu8hN+Dg== X-Received: by 2002:a17:902:e101:: with SMTP id cc1mr17867671plb.129.1554014524195; Sat, 30 Mar 2019 23:42:04 -0700 (PDT) Received: from brianvv.svl.corp.google.com ([2620:15c:2c4:201:c1c8:2119:1010:59e0]) by smtp.gmail.com with ESMTPSA id p88sm10653281pfa.80.2019.03.30.23.42.03 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 30 Mar 2019 23:42:03 -0700 (PDT) From: Brian Vazquez To: Brian Vazquez , Alexei Starovoitov , "David S . Miller" Cc: =?utf-8?q?Maciej_=C5=BBenczykowski?= , linux-kernel@vger.kernel.org, netdev@vger.kernel.org Subject: [PATCH] bpf: do not start from first bucket if elem is not found on a htab Date: Sat, 30 Mar 2019 23:41:29 -0700 Message-Id: <20190331064129.31702-1-brianvv.kernel@gmail.com> X-Mailer: git-send-email 2.21.0.392.gf8f6787159e-goog MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Brian Vazquez When you want to traverse an entire map using BPF_MAP_GET_NEXT_KEY and key provided is not present due to a deletion you will start iterating the map from the beginning without noticing it. This patch changes the starting bucket in those situations to the bucket where key was suppossed to be. Note that you can still get stuck in the same bucket but it is less likely than getting stuck in a loop restarting from the beginning of the entire map. Signed-off-by: Brian Vazquez Signed-off-by: Maciej Żenczykowski --- kernel/bpf/hashtab.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index fed15cf94dca6..eea046d269f51 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -611,11 +611,14 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) hash = htab_map_hash(key, key_size, htab->hashrnd); - head = select_bucket(htab, hash); + /* keep track of current bucket */ + i = hash & (htab->n_buckets - 1); + head = select_bucket(htab, i); /* lookup the key */ l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets); + /* this will start looking from bucket i */ if (!l) goto find_first_elem; @@ -630,7 +633,6 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) } /* no more elements in this hash list, go to the next bucket */ - i = hash & (htab->n_buckets - 1); i++; find_first_elem: