From patchwork Fri Sep 29 19:56:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jacob Satterfield X-Patchwork-Id: 13404783 X-Patchwork-Delegate: paul@paul-moore.com Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id DA837E728E4 for ; Fri, 29 Sep 2023 19:56:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233233AbjI2T4q (ORCPT ); Fri, 29 Sep 2023 15:56:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60880 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233310AbjI2T4p (ORCPT ); Fri, 29 Sep 2023 15:56:45 -0400 Received: from mail-qk1-x733.google.com (mail-qk1-x733.google.com [IPv6:2607:f8b0:4864:20::733]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 53CE81A7 for ; Fri, 29 Sep 2023 12:56:41 -0700 (PDT) Received: by mail-qk1-x733.google.com with SMTP id af79cd13be357-77421a47db6so739642585a.0 for ; Fri, 29 Sep 2023 12:56:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696017400; x=1696622200; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=35CJJpDoVj/GETigOLPSGUH+BDkgMwBAtDEZtn70ROg=; b=NqyvoXHsLp54/XtevMWqgUq1QFPYcRh1CQHt5k/w84QfI2QSgkPhuTryzDBYjJUktt wWdW/45MKwku6D4dO41ycoskxEzFWErvzxTrQjRXAqo/hB9P7Qmr6LCLkEI7u6RvuT10 9h/KomjwHwkd8MVAUr29/rQdx0G1hlpAFFLrTBJzSptw/Iox9kBkAUYgOOFwlyn0mE/y O62nstGyG37VH+waQGM+tJq1luri+RqpXyzyjBTS26z7tT1u9PYtL/F7VjeJuc2RJmgj 7NWtCnz6BR559U/bWfrmz81wKvR3KhR2ffabOCrRAk0gVBnWElnytlwK3DMTfz01v8vM 9xZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696017400; x=1696622200; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=35CJJpDoVj/GETigOLPSGUH+BDkgMwBAtDEZtn70ROg=; b=nVSoBMdJCiEWq3L0WJPfn1KsJNQwC0wlp8nyHiUtNTLGQEKngvPWWD1/3l0cbQJTed 1WQEQtG76eqZkQjNkM+kd4QjrP5MSb8sw6hdW2L0DNKGMYWiJm7kSH75BJVjTkKt52cr sRVmYkCSmQLQwxbSBt5lj4HU2d31VinMuTZW9d3KMhU2NpSw6UD9ZgWuo/uZfkFcVvV8 sAliAoSX3nfBd5XZ96OB/wL80ZrTwajkMffif+58SHWnuVfFksHEnRGVfiKFpfhZ2BkW RtfPLW/VeqfdbEcGRxYQqv+en67Ly4Bjqi4A6seO63wkA/TekbGzCU8PVfPC+gOin5Xe n/EA== X-Gm-Message-State: AOJu0Yydhrfb6qq9dNkdcz43F3yDLLiAkVqhSLCZuWEqZeJWmEr84O4c xpc8QcMpM6FfomyEIq/DkldnMuwAXHM= X-Google-Smtp-Source: AGHT+IHirwBco23cWVslM0wUDTLTxAlzXettjx0I43DiAbWrxxpAd8z9l84jJ5KeysYI5xXD0DJ+Nw== X-Received: by 2002:a05:620a:40c4:b0:76f:1318:d7d1 with SMTP id g4-20020a05620a40c400b0076f1318d7d1mr6565004qko.75.1696017400008; Fri, 29 Sep 2023 12:56:40 -0700 (PDT) Received: from 5bc235456ce7.evoforge.org (ec2-52-70-167-183.compute-1.amazonaws.com. [52.70.167.183]) by smtp.gmail.com with ESMTPSA id t6-20020a05620a034600b00767e98535b7sm5795291qkm.67.2023.09.29.12.56.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 29 Sep 2023 12:56:39 -0700 (PDT) From: Jacob Satterfield To: selinux@vger.kernel.org Cc: Jacob Satterfield , stephen.smalley.work@gmail.com, paul@paul-moore.com, omosnace@redhat.com Subject: [PATCH 1/4] selinux: simplify avtab_insert_node() prototype Date: Fri, 29 Sep 2023 19:56:12 +0000 Message-ID: <20230929195617.65120-2-jsatterfield.linux@gmail.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20230929195617.65120-1-jsatterfield.linux@gmail.com> References: <20230929195617.65120-1-jsatterfield.linux@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org __hashtab_insert() in hashtab.h has a cleaner interface that allows the caller to specify the chain node location that the new node is being inserted into so that it can update the node that currently occupies it. Signed-off-by: Jacob Satterfield Reviewed-by: Stephen Smalley --- security/selinux/ss/avtab.c | 20 +++++++------------- 1 file changed, 7 insertions(+), 13 deletions(-) diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 095b8cd24806..8751a602ead2 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -67,8 +67,7 @@ static inline u32 avtab_hash(const struct avtab_key *keyp, u32 mask) } static struct avtab_node* -avtab_insert_node(struct avtab *h, u32 hvalue, - struct avtab_node *prev, +avtab_insert_node(struct avtab *h, struct avtab_node **dst, const struct avtab_key *key, const struct avtab_datum *datum) { struct avtab_node *newnode; @@ -90,15 +89,8 @@ avtab_insert_node(struct avtab *h, u32 hvalue, newnode->datum.u.data = datum->u.data; } - if (prev) { - newnode->next = prev->next; - prev->next = newnode; - } else { - struct avtab_node **n = &h->htable[hvalue]; - - newnode->next = *n; - *n = newnode; - } + newnode->next = *dst; + *dst = newnode; h->nel++; return newnode; @@ -138,7 +130,8 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key, break; } - newnode = avtab_insert_node(h, hvalue, prev, key, datum); + newnode = avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue], + key, datum); if (!newnode) return -ENOMEM; @@ -178,7 +171,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h, key->target_class < cur->key.target_class) break; } - return avtab_insert_node(h, hvalue, prev, key, datum); + return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue], + key, datum); } /* This search function returns a node pointer, and can be used in From patchwork Fri Sep 29 19:56:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jacob Satterfield X-Patchwork-Id: 13404782 X-Patchwork-Delegate: paul@paul-moore.com Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4224FE728DE for ; Fri, 29 Sep 2023 19:56:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233179AbjI2T4p (ORCPT ); Fri, 29 Sep 2023 15:56:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60814 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233260AbjI2T4o (ORCPT ); Fri, 29 Sep 2023 15:56:44 -0400 Received: from mail-qv1-xf34.google.com (mail-qv1-xf34.google.com [IPv6:2607:f8b0:4864:20::f34]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 489DB1BD for ; Fri, 29 Sep 2023 12:56:42 -0700 (PDT) Received: by mail-qv1-xf34.google.com with SMTP id 6a1803df08f44-65b08bbd8b1so62627276d6.2 for ; Fri, 29 Sep 2023 12:56:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696017401; x=1696622201; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=k/MRuryTfTYas9thOxLxXlU5pgemWnUJNDOe7pAn7Yw=; b=A4UHtu5+vmzDEW0e1kawVmWOZUaAPX28ZFJoRi8ApvFIZ5qcz6Cf/eu21qt4pqyVIO 67SYO+3ucRprLeKwnK7BwyhZFRoPugc02sSYkM5MdN9Tg042ONGRIc7G4TgfaJEU8WnI 9RDwGhR+ZTc4dwLEi0qlrSGyf4r6zxTtlWY9hdtXAmrKuO0adntm/wy+XYgIk0uW1GHs 2iKXs+lbdMJ/zbqH69uOMl4jNAVj5PUeAmnBkxRKM0Dr8BOQxL9VnFEgNqfgmzUprnRI 1lOEoYxiDuBcqVFJvXqerI6ClRhYraZIAmlOa2vF2DchP+33rVv5MaPdvJ9Nt5oW1E1F v/qA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696017401; x=1696622201; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=k/MRuryTfTYas9thOxLxXlU5pgemWnUJNDOe7pAn7Yw=; b=MTxwq1iF1zsd5cUJbnLSuFv5yNBKCpBQnb6WlNqHE2u9kB95UGemP9u0pfNjsF4+dh oBqvch8amLT7Xv4IUVR/vHHiux1x3iHO8l9OIS1so44vEwznYVvu2WJrrGMQGGf6IS9i NNOB150wlaBR1ni2Bf4CH7+vVl0hR0/WY2zrUWNvAxJ4DQdTcWH/hI5N/fRVm6CU3FvP 0481h5pRCNJTUMXG2kIAjfagcvQaFitKprCabjp5HLpkIKbGlUhBTA+PmShdJdgC+8xS lTn60vJ036qDuIfdqs7eQjyzxWpE3UmQPzK1uFO4qABHnyN8jGE7BN3ucDtkZWskLcCU aEog== X-Gm-Message-State: AOJu0Yx0lIy5apOJeA9ZGMqIg/1uBMbM/d19gXRsGQdA0Q3JNgFwxE7V 15mn4rkzFzY6HcX+4ndHmJKhiunZ5Ew= X-Google-Smtp-Source: AGHT+IHXF5U5crAgQ8U/mT4ncUuW8gapXBg9P0de+5PKhTr5CE9OzLAV4OC4pgZgAvEbgrCb/1eX4w== X-Received: by 2002:a0c:f1c1:0:b0:658:9168:e6b6 with SMTP id u1-20020a0cf1c1000000b006589168e6b6mr5051388qvl.52.1696017400987; Fri, 29 Sep 2023 12:56:40 -0700 (PDT) Received: from 5bc235456ce7.evoforge.org (ec2-52-70-167-183.compute-1.amazonaws.com. [52.70.167.183]) by smtp.gmail.com with ESMTPSA id t6-20020a05620a034600b00767e98535b7sm5795291qkm.67.2023.09.29.12.56.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 29 Sep 2023 12:56:40 -0700 (PDT) From: Jacob Satterfield To: selinux@vger.kernel.org Cc: Jacob Satterfield , stephen.smalley.work@gmail.com, paul@paul-moore.com, omosnace@redhat.com Subject: [PATCH 2/4] selinux: refactor avtab_node comparisons Date: Fri, 29 Sep 2023 19:56:13 +0000 Message-ID: <20230929195617.65120-3-jsatterfield.linux@gmail.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20230929195617.65120-1-jsatterfield.linux@gmail.com> References: <20230929195617.65120-1-jsatterfield.linux@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org In four separate functions within avtab, the same comparison logic is used. The only difference is how the result is handled or whether there is a unique specifier value to be checked for or used. Extracting this functionality into the avtab_node_cmp() function unifies the comparison logic between searching and insertion and gets rid of duplicative code so that the implementation is easier to maintain. Signed-off-by: Jacob Satterfield Reviewed-by: Stephen Smalley --- security/selinux/ss/avtab.c | 101 +++++++++++++++--------------------- 1 file changed, 41 insertions(+), 60 deletions(-) diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 8751a602ead2..1cd4fed30bf7 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -96,12 +96,34 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst, return newnode; } +static int avtab_node_cmp(const struct avtab_key *key1, + const struct avtab_key *key2) +{ + u16 specified = key1->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); + + if (key1->source_type == key2->source_type && + key1->target_type == key2->target_type && + key1->target_class == key2->target_class && + (specified & key2->specified)) + return 0; + if (key1->source_type < key2->source_type) + return -1; + if (key1->source_type == key2->source_type && + key1->target_type < key2->target_type) + return -1; + if (key1->source_type == key2->source_type && + key1->target_type == key2->target_type && + key1->target_class < key2->target_class) + return -1; + return 1; +} + static int avtab_insert(struct avtab *h, const struct avtab_key *key, const struct avtab_datum *datum) { u32 hvalue; struct avtab_node *prev, *cur, *newnode; - u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); + int cmp; if (!h || !h->nslot || h->nel == U32_MAX) return -EINVAL; @@ -110,23 +132,11 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key, for (prev = NULL, cur = h->htable[hvalue]; cur; prev = cur, cur = cur->next) { - if (key->source_type == cur->key.source_type && - key->target_type == cur->key.target_type && - key->target_class == cur->key.target_class && - (specified & cur->key.specified)) { - /* extended perms may not be unique */ - if (specified & AVTAB_XPERMS) - break; + cmp = avtab_node_cmp(key, &cur->key); + /* extended perms may not be unique */ + if (unlikely(cmp == 0 && !(key->specified & AVTAB_XPERMS))) return -EEXIST; - } - if (key->source_type < cur->key.source_type) - break; - if (key->source_type == cur->key.source_type && - key->target_type < cur->key.target_type) - break; - if (key->source_type == cur->key.source_type && - key->target_type == cur->key.target_type && - key->target_class < cur->key.target_class) + if (cmp <= 0) break; } @@ -148,7 +158,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h, { u32 hvalue; struct avtab_node *prev, *cur; - u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); + int cmp; if (!h || !h->nslot || h->nel == U32_MAX) return NULL; @@ -156,19 +166,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h, for (prev = NULL, cur = h->htable[hvalue]; cur; prev = cur, cur = cur->next) { - if (key->source_type == cur->key.source_type && - key->target_type == cur->key.target_type && - key->target_class == cur->key.target_class && - (specified & cur->key.specified)) - break; - if (key->source_type < cur->key.source_type) - break; - if (key->source_type == cur->key.source_type && - key->target_type < cur->key.target_type) - break; - if (key->source_type == cur->key.source_type && - key->target_type == cur->key.target_type && - key->target_class < cur->key.target_class) + cmp = avtab_node_cmp(key, &cur->key); + if (cmp <= 0) break; } return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue], @@ -183,7 +182,7 @@ struct avtab_node *avtab_search_node(struct avtab *h, { u32 hvalue; struct avtab_node *cur; - u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); + int cmp; if (!h || !h->nslot) return NULL; @@ -191,20 +190,10 @@ struct avtab_node *avtab_search_node(struct avtab *h, hvalue = avtab_hash(key, h->mask); for (cur = h->htable[hvalue]; cur; cur = cur->next) { - if (key->source_type == cur->key.source_type && - key->target_type == cur->key.target_type && - key->target_class == cur->key.target_class && - (specified & cur->key.specified)) + cmp = avtab_node_cmp(key, &cur->key); + if (cmp == 0) return cur; - - if (key->source_type < cur->key.source_type) - break; - if (key->source_type == cur->key.source_type && - key->target_type < cur->key.target_type) - break; - if (key->source_type == cur->key.source_type && - key->target_type == cur->key.target_type && - key->target_class < cur->key.target_class) + if (cmp < 0) break; } return NULL; @@ -213,27 +202,19 @@ struct avtab_node *avtab_search_node(struct avtab *h, struct avtab_node* avtab_search_node_next(struct avtab_node *node, u16 specified) { + struct avtab_key tmp_key; struct avtab_node *cur; + int cmp; if (!node) return NULL; - - specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); + tmp_key = node->key; + tmp_key.specified = specified; for (cur = node->next; cur; cur = cur->next) { - if (node->key.source_type == cur->key.source_type && - node->key.target_type == cur->key.target_type && - node->key.target_class == cur->key.target_class && - (specified & cur->key.specified)) + cmp = avtab_node_cmp(&tmp_key, &cur->key); + if (cmp == 0) return cur; - - if (node->key.source_type < cur->key.source_type) - break; - if (node->key.source_type == cur->key.source_type && - node->key.target_type < cur->key.target_type) - break; - if (node->key.source_type == cur->key.source_type && - node->key.target_type == cur->key.target_type && - node->key.target_class < cur->key.target_class) + if (cmp < 0) break; } return NULL; From patchwork Fri Sep 29 19:56:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jacob Satterfield X-Patchwork-Id: 13404784 X-Patchwork-Delegate: paul@paul-moore.com Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7BD38E728E2 for ; Fri, 29 Sep 2023 19:56:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233208AbjI2T4q (ORCPT ); Fri, 29 Sep 2023 15:56:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60876 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233233AbjI2T4p (ORCPT ); Fri, 29 Sep 2023 15:56:45 -0400 Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com [IPv6:2607:f8b0:4864:20::72b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 45068B4 for ; Fri, 29 Sep 2023 12:56:43 -0700 (PDT) Received: by mail-qk1-x72b.google.com with SMTP id af79cd13be357-774141bb415so822769485a.3 for ; Fri, 29 Sep 2023 12:56:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696017402; x=1696622202; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ODNXzeNNHF/CByGHAciz5iR0U8C1f17a+mgg9DaKACY=; b=QZ3SksYndFEKKhhEbQOfa/mCbCCAqgV95M3h7RGvBbd8D5DMSE3j62H3pUUpJwpRI6 a1QIyinV3nv5LPpANNXxDLlfBnYB8rubwg0wf3LkMaEYzcZ2uwfoEwVbMbdSTPJvkW91 29/X+6Dzb59JeYE0x529Wwd48AfaG+olDcrR+z3jBK0ZC5ctUTd3OPlzTAIPiHPZy2JM tX562/XAtxTtIgycK5D1zQaF+1BPO6P5E6tvR2mOcy28WDmyuSKZUj0utcRYPuMnMZAN Rqam1ABBz4tHuFSfCbm0wEAOtlJzXwtSVrFexHX5ybZKoTdn6kUo/n+fzAPMzEZZZ2qA rxIw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696017402; x=1696622202; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ODNXzeNNHF/CByGHAciz5iR0U8C1f17a+mgg9DaKACY=; b=tZoy3SAw+qCkcL9jrXe4w7MDqKXtef4ww2yPBTdC7weAO20yaGV8v/7cYDWreVkN1G JJlSh+3ilmVL3CFekrWe3vdLY8b7w4cHzDx5+7LsMC3zlYunEpvhYGAu0Mwk+HSQ3H01 Fb5ZLgIIYs8TiyO5DjOKb/wlbCxd6H1oh5pD14fmFhC6qOpQqLh2VzsWG5R+l418PvHG DCFv9JkyzOdWgDAXK3khbdCLR/hqe4wONaKrKthb/hvnMRu47oXgJBNImfPqCYJx2MVi tvmfmJMpvldZzz75rXmv7cVeBTZxSQTALh+V3BYL2a0E2s4+vIfTdNFmIb8uddKcE3Rw Jz0w== X-Gm-Message-State: AOJu0YyJX2fBmPYOefX91EGNJb+HYgmozObRjxVBPTIys6kYA7YzQ8HF ECJUHx7diOz1GhcZbHhTIYWYGlPR81E= X-Google-Smtp-Source: AGHT+IElLdGVnUC6cpBsO1/E6lUB+yAzM+ix1AHWHVZCpbodHBPAUxjxsb3JBnjAesGM2gJmBmeT+A== X-Received: by 2002:a05:620a:470c:b0:773:ad9b:4c81 with SMTP id bs12-20020a05620a470c00b00773ad9b4c81mr6248576qkb.23.1696017401939; Fri, 29 Sep 2023 12:56:41 -0700 (PDT) Received: from 5bc235456ce7.evoforge.org (ec2-52-70-167-183.compute-1.amazonaws.com. [52.70.167.183]) by smtp.gmail.com with ESMTPSA id t6-20020a05620a034600b00767e98535b7sm5795291qkm.67.2023.09.29.12.56.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 29 Sep 2023 12:56:41 -0700 (PDT) From: Jacob Satterfield To: selinux@vger.kernel.org Cc: Jacob Satterfield , stephen.smalley.work@gmail.com, paul@paul-moore.com, omosnace@redhat.com Subject: [PATCH 3/4] selinux: avtab iteration macros Date: Fri, 29 Sep 2023 19:56:14 +0000 Message-ID: <20230929195617.65120-4-jsatterfield.linux@gmail.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20230929195617.65120-1-jsatterfield.linux@gmail.com> References: <20230929195617.65120-1-jsatterfield.linux@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Similar to the list_for_each macros in list.h, this patch adds two macros that iterates an avtab_node linked list (avtab_chain_for_each and avtab_chain_for_each_prev). This has two benefits: it reduces the amount of duplicative code for iteration and it makes changes to the underlying hashtable data structure easier as there are fewer places to update. Signed-off-by: Jacob Satterfield --- security/selinux/ss/avtab.c | 40 ++++++++++++++++--------------------- 1 file changed, 17 insertions(+), 23 deletions(-) diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 1cd4fed30bf7..e8046eda7140 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -27,6 +27,13 @@ static struct kmem_cache *avtab_node_cachep __ro_after_init; static struct kmem_cache *avtab_xperms_cachep __ro_after_init; +#define avtab_chain_for_each(pos, tab, slot) \ + for (pos = (tab)->htable[slot]; pos; pos = pos->next) + +#define avtab_chain_for_each_prev(pos, prev, tab, slot) \ + for (prev = NULL, pos = (tab)->htable[slot]; pos; \ + prev = pos, pos = pos->next) + /* Based on MurmurHash3, written by Austin Appleby and placed in the * public domain. */ @@ -129,9 +136,7 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key, return -EINVAL; hvalue = avtab_hash(key, h->mask); - for (prev = NULL, cur = h->htable[hvalue]; - cur; - prev = cur, cur = cur->next) { + avtab_chain_for_each_prev(cur, prev, h, hvalue) { cmp = avtab_node_cmp(key, &cur->key); /* extended perms may not be unique */ if (unlikely(cmp == 0 && !(key->specified & AVTAB_XPERMS))) @@ -163,9 +168,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h, if (!h || !h->nslot || h->nel == U32_MAX) return NULL; hvalue = avtab_hash(key, h->mask); - for (prev = NULL, cur = h->htable[hvalue]; - cur; - prev = cur, cur = cur->next) { + avtab_chain_for_each_prev(cur, prev, h, hvalue) { cmp = avtab_node_cmp(key, &cur->key); if (cmp <= 0) break; @@ -180,16 +183,13 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h, struct avtab_node *avtab_search_node(struct avtab *h, const struct avtab_key *key) { - u32 hvalue; struct avtab_node *cur; int cmp; if (!h || !h->nslot) return NULL; - hvalue = avtab_hash(key, h->mask); - for (cur = h->htable[hvalue]; cur; - cur = cur->next) { + avtab_chain_for_each(cur, h, avtab_hash(key, h->mask)) { cmp = avtab_node_cmp(key, &cur->key); if (cmp == 0) return cur; @@ -223,20 +223,17 @@ avtab_search_node_next(struct avtab_node *node, u16 specified) void avtab_destroy(struct avtab *h) { u32 i; - struct avtab_node *cur, *temp; + struct avtab_node *cur; if (!h) return; for (i = 0; i < h->nslot; i++) { - cur = h->htable[i]; - while (cur) { - temp = cur; - cur = cur->next; - if (temp->key.specified & AVTAB_XPERMS) + avtab_chain_for_each(cur, h, i) { + if (cur->key.specified & AVTAB_XPERMS) kmem_cache_free(avtab_xperms_cachep, - temp->datum.u.xperms); - kmem_cache_free(avtab_node_cachep, temp); + cur->datum.u.xperms); + kmem_cache_free(avtab_node_cachep, cur); } } kvfree(h->htable); @@ -307,10 +304,8 @@ void avtab_hash_eval(struct avtab *h, const char *tag) if (cur) { slots_used++; chain_len = 0; - while (cur) { + avtab_chain_for_each(cur, h, i) chain_len++; - cur = cur->next; - } if (chain_len > max_chain_len) max_chain_len = chain_len; @@ -593,8 +588,7 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp) return rc; for (i = 0; i < a->nslot; i++) { - for (cur = a->htable[i]; cur; - cur = cur->next) { + avtab_chain_for_each(cur, a, i) { rc = avtab_write_item(p, cur, fp); if (rc) return rc; From patchwork Fri Sep 29 19:56:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jacob Satterfield X-Patchwork-Id: 13404785 X-Patchwork-Delegate: paul@paul-moore.com Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4E4DFE728E3 for ; Fri, 29 Sep 2023 19:56:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233260AbjI2T4r (ORCPT ); Fri, 29 Sep 2023 15:56:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:45018 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233257AbjI2T4q (ORCPT ); Fri, 29 Sep 2023 15:56:46 -0400 Received: from mail-qk1-x735.google.com (mail-qk1-x735.google.com [IPv6:2607:f8b0:4864:20::735]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4D562113 for ; Fri, 29 Sep 2023 12:56:44 -0700 (PDT) Received: by mail-qk1-x735.google.com with SMTP id af79cd13be357-7740c8509c8so912391485a.3 for ; Fri, 29 Sep 2023 12:56:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696017403; x=1696622203; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=AHCP+t63RHpOqaUrds4qKXl3q/8PkxR/0zjfBrnXpnY=; b=UgkNECe/LJgYs6uj8XExkwBENUQABPTDk7rnnuhcxroj2McCv8YF8/hqScGxP4BChu kxni669XTsHpmXndFFH9uH1UUU8+eP2LO52X3eJK/3BVM+ac7dolhD7c7lSCz8FCBytv FFM72GvcF/XKoiyodc/6sBpCT22BoCvULJb2+p6TYWhS2ufN81qum8suaTVhIvsftcc3 ZStnJY2bDnmBH+WxfPgM0vICgCnc1uMDO3AyGCNUgQTx0g67A9ILtKUZIWGytftT/Dcf JzLPhKLVkfSNjd2D7QGGy3WhXHaikpiyyFSi2MlBQlcqM6Sbmvmz8dFgF4fBb6PScBug /+Eg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696017403; x=1696622203; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=AHCP+t63RHpOqaUrds4qKXl3q/8PkxR/0zjfBrnXpnY=; b=bC9sFOT0Sdz81Rth0LyXAOESbn9QDOOlKzhZ85NAuJEmUMUI4+DVP4Byu9BW1qTUE6 JRG2dsxabpL5DE7xQHNeojNZqEdGqt/Jnygu1I7Eu2LAkhNvKV6scacXQAxBXtHLJpVQ qFajfpOxnQ1FFgjIQBC/LTrQvADoRgdmmNJO4sLuISuPtTRV9S/shFd88j4Vt0r4jfKX ZHLFlkpOOOrLZ2tFgHm4QZ9C76Vq9Nxk1/LKrJljfyFJZnR0sV0hGekmc2YsRGjMxkvq rkXe6B6LGXRS6ZZCuSCDNKAtAxYflNwF/4HKygAryp9hSHvOOD/6Y2JhUyT7ux9IYQig RUGQ== X-Gm-Message-State: AOJu0YziDZGgBv0inw+C1cCxx7gxxEnTkuG86t7CubJB33nWD8CqGi7D or2eQRZZSlhWtyhLQaagerL3jI+sDO8= X-Google-Smtp-Source: AGHT+IH4Jz5Hs7r3hk5w1Ib7NgnJCZmUD5zZbDrD682pQqZE6Upih70X8bozo7jUDjQK3d9lNpqoPg== X-Received: by 2002:a05:620a:942:b0:773:a83f:4a66 with SMTP id w2-20020a05620a094200b00773a83f4a66mr4915787qkw.36.1696017402906; Fri, 29 Sep 2023 12:56:42 -0700 (PDT) Received: from 5bc235456ce7.evoforge.org (ec2-52-70-167-183.compute-1.amazonaws.com. [52.70.167.183]) by smtp.gmail.com with ESMTPSA id t6-20020a05620a034600b00767e98535b7sm5795291qkm.67.2023.09.29.12.56.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 29 Sep 2023 12:56:42 -0700 (PDT) From: Jacob Satterfield To: selinux@vger.kernel.org Cc: Jacob Satterfield , stephen.smalley.work@gmail.com, paul@paul-moore.com, omosnace@redhat.com Subject: [PATCH 4/4] selinux: use arrays for avtab hashtable nodes Date: Fri, 29 Sep 2023 19:56:15 +0000 Message-ID: <20230929195617.65120-5-jsatterfield.linux@gmail.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20230929195617.65120-1-jsatterfield.linux@gmail.com> References: <20230929195617.65120-1-jsatterfield.linux@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The current avtab hashtable employs a separate chaining collision resolution strategy where each bucket/chain holds an ordered linked list of pointers to kmem_cache allocated avtab_node elements. On Fedora 38 (x86_64) using the default policy, avtab_node_cachep uses 573 slabs each containing 170 objects totaling 2,337,840 bytes. A call to kmem_cache_zalloc() is required for every single rule, which in the default policy is currently 96,730 and continually rising. When both sets of avtab_node (regular and cond.) are turned into arrays with the hash table slot indexing into it rather than a pointer, then this results in only 2 additional kvcalloc() calls and the complete removal of the kmem_cache itself. Due to how conditional rules are written in the binary policy, the code responsible for loading does not know how many conditional rules there are before creating the avtab structure. Instead, it was using the number of elements in the non-conditional avtab as a hint and allocates the hash table based on it. Therefore, a two-pass algorithm is now used to calculate the rule count before allocating the avtab nodes array. With the current refpolicy and default Fedora policy, this causes the number of hash slots for the conditional array to become 4096 instead of 32768. This results in a savings of 224KB of heap memory. The caching characteristics of iterating a single array are better due to locality of reference. Running "perf stat -r 100 -d load_policy" has shown a runtime reduction of at least 10% on a Fedora 38 x86_64 VM with this single patch. Future patches focused on improving the hash table's collision resolution strategy and array layout (struct-of-arrays vs. array-of-structs) may elicit even more caching and therefore runtime performance improvements. Signed-off-by: Jacob Satterfield --- security/selinux/ss/avtab.c | 47 ++++++++++++++++++++----------- security/selinux/ss/avtab.h | 4 ++- security/selinux/ss/conditional.c | 37 ++++++++++++++++-------- security/selinux/ss/conditional.h | 2 +- 4 files changed, 59 insertions(+), 31 deletions(-) diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index e8046eda7140..67bf96d70923 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -24,7 +24,6 @@ #include "avtab.h" #include "policydb.h" -static struct kmem_cache *avtab_node_cachep __ro_after_init; static struct kmem_cache *avtab_xperms_cachep __ro_after_init; #define avtab_chain_for_each(pos, tab, slot) \ @@ -79,17 +78,15 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst, { struct avtab_node *newnode; struct avtab_extended_perms *xperms; - newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); - if (newnode == NULL) + if (h->nel == h->nnodes) return NULL; + newnode = &h->nodes[h->nel]; newnode->key = *key; if (key->specified & AVTAB_XPERMS) { xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL); - if (xperms == NULL) { - kmem_cache_free(avtab_node_cachep, newnode); + if (xperms == NULL) return NULL; - } *xperms = *(datum->u.xperms); newnode->datum.u.xperms = xperms; } else { @@ -233,11 +230,13 @@ void avtab_destroy(struct avtab *h) if (cur->key.specified & AVTAB_XPERMS) kmem_cache_free(avtab_xperms_cachep, cur->datum.u.xperms); - kmem_cache_free(avtab_node_cachep, cur); } } kvfree(h->htable); + kvfree(h->nodes); h->htable = NULL; + h->nodes = NULL; + h->nnodes = 0; h->nel = 0; h->nslot = 0; h->mask = 0; @@ -246,20 +245,28 @@ void avtab_destroy(struct avtab *h) void avtab_init(struct avtab *h) { h->htable = NULL; + h->nodes = NULL; + h->nnodes = 0; h->nel = 0; h->nslot = 0; h->mask = 0; } -static int avtab_alloc_common(struct avtab *h, u32 nslot) +static int avtab_alloc_common(struct avtab *h, u32 nslot, u32 nrules) { if (!nslot) return 0; - h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL); + h->htable = kvcalloc(nslot, sizeof(*h->htable), GFP_KERNEL); if (!h->htable) return -ENOMEM; - + h->nodes = kvcalloc(nrules, sizeof(*h->nodes), GFP_KERNEL); + if (!h->nodes) { + kvfree(h->htable); + h->htable = NULL; + return -ENOMEM; + } + h->nnodes = nrules; h->nslot = nslot; h->mask = nslot - 1; return 0; @@ -275,7 +282,7 @@ int avtab_alloc(struct avtab *h, u32 nrules) if (nslot > MAX_AVTAB_HASH_BUCKETS) nslot = MAX_AVTAB_HASH_BUCKETS; - rc = avtab_alloc_common(h, nslot); + rc = avtab_alloc_common(h, nslot, nrules); if (rc) return rc; } @@ -286,7 +293,7 @@ int avtab_alloc(struct avtab *h, u32 nrules) int avtab_alloc_dup(struct avtab *new, const struct avtab *orig) { - return avtab_alloc_common(new, orig->nslot); + return avtab_alloc_common(new, orig->nslot, orig->nel); } #ifdef CONFIG_SECURITY_SELINUX_DEBUG @@ -335,7 +342,7 @@ static const uint16_t spec_order[] = { int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, int (*insertf)(struct avtab *a, const struct avtab_key *k, const struct avtab_datum *d, void *p), - void *p) + void *p, u32 *nrules) { __le16 buf16[4]; u16 enabled; @@ -409,6 +416,10 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, if (val & spec_order[i]) { key.specified = spec_order[i] | enabled; datum.u.data = le32_to_cpu(buf32[items++]); + if (nrules) { + (*nrules)++; + continue; + } rc = insertf(a, &key, &datum, p); if (rc) return rc; @@ -487,6 +498,11 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, pr_err("SELinux: avtab: invalid type\n"); return -EINVAL; } + + if (nrules) { + (*nrules)++; + return 0; + } return insertf(a, &key, &datum, p); } @@ -520,7 +536,7 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol) goto bad; for (i = 0; i < nel; i++) { - rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); + rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL, NULL); if (rc) { if (rc == -ENOMEM) pr_err("SELinux: avtab: out of memory\n"); @@ -600,9 +616,6 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp) void __init avtab_cache_init(void) { - avtab_node_cachep = kmem_cache_create("avtab_node", - sizeof(struct avtab_node), - 0, SLAB_PANIC, NULL); avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms", sizeof(struct avtab_extended_perms), 0, SLAB_PANIC, NULL); diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h index 3c3904bf02b0..5e465be6f057 100644 --- a/security/selinux/ss/avtab.h +++ b/security/selinux/ss/avtab.h @@ -82,6 +82,8 @@ struct avtab_node { struct avtab { struct avtab_node **htable; + struct avtab_node *nodes; + u32 nnodes; /* number of nodes */ u32 nel; /* number of elements */ u32 nslot; /* number of hash slots */ u32 mask; /* mask to compute hash func */ @@ -104,7 +106,7 @@ struct policydb; int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, int (*insert)(struct avtab *a, const struct avtab_key *k, const struct avtab_datum *d, void *p), - void *p); + void *p, u32 *nrules); int avtab_read(struct avtab *a, void *fp, struct policydb *pol); int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp); diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c index 81ff676f209a..bbd35b35b79d 100644 --- a/security/selinux/ss/conditional.c +++ b/security/selinux/ss/conditional.c @@ -140,7 +140,7 @@ void cond_policydb_init(struct policydb *p) static void cond_node_destroy(struct cond_node *node) { kfree(node->expr.nodes); - /* the avtab_ptr_t nodes are destroyed by the avtab */ + /* the actual nodes were destroyed by avtab_destroy() */ kfree(node->true_list.nodes); kfree(node->false_list.nodes); } @@ -323,7 +323,8 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k, static int cond_read_av_list(struct policydb *p, void *fp, struct cond_av_list *list, - struct cond_av_list *other) + struct cond_av_list *other, + u32 *nrules) { int rc; __le32 buf[1]; @@ -347,7 +348,7 @@ static int cond_read_av_list(struct policydb *p, void *fp, for (i = 0; i < len; i++) { data.dst = &list->nodes[i]; rc = avtab_read_item(&p->te_cond_avtab, fp, p, cond_insertf, - &data); + &data, nrules); if (rc) { kfree(list->nodes); list->nodes = NULL; @@ -373,7 +374,8 @@ static int expr_node_isvalid(struct policydb *p, struct cond_expr_node *expr) return 1; } -static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp) +static int cond_read_node(struct policydb *p, struct cond_node *node, + void *fp, u32 *nrules) { __le32 buf[2]; u32 i, len; @@ -407,16 +409,17 @@ static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp) return -EINVAL; } - rc = cond_read_av_list(p, fp, &node->true_list, NULL); + rc = cond_read_av_list(p, fp, &node->true_list, NULL, nrules); if (rc) return rc; - return cond_read_av_list(p, fp, &node->false_list, &node->true_list); + return cond_read_av_list(p, fp, &node->false_list, &node->true_list, nrules); } -int cond_read_list(struct policydb *p, void *fp) +int cond_read_list(struct policydb *p, struct policy_file *fp) { __le32 buf[1]; - u32 i, len; + struct policy_file tmp_fp; + u32 i, len, nrules; int rc; rc = next_entry(buf, fp, sizeof(buf)); @@ -428,15 +431,25 @@ int cond_read_list(struct policydb *p, void *fp) p->cond_list = kcalloc(len, sizeof(*p->cond_list), GFP_KERNEL); if (!p->cond_list) return -ENOMEM; + p->cond_list_len = len; + + /* first pass to only calculate the avrule count */ + tmp_fp = *fp; + nrules = 0; + for (i = 0; i < len; i++) { + rc = cond_read_node(p, &p->cond_list[i], &tmp_fp, &nrules); + if (rc) + goto err; + cond_node_destroy(&p->cond_list[i]); + } - rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel); + rc = avtab_alloc(&(p->te_cond_avtab), nrules); if (rc) goto err; - p->cond_list_len = len; - + /* second pass to read in the conditional nodes */ for (i = 0; i < len; i++) { - rc = cond_read_node(p, &p->cond_list[i], fp); + rc = cond_read_node(p, &p->cond_list[i], fp, NULL); if (rc) goto err; } diff --git a/security/selinux/ss/conditional.h b/security/selinux/ss/conditional.h index 5a7b51278dc6..62a12d00cac9 100644 --- a/security/selinux/ss/conditional.h +++ b/security/selinux/ss/conditional.h @@ -70,7 +70,7 @@ int cond_destroy_bool(void *key, void *datum, void *p); int cond_index_bool(void *key, void *datum, void *datap); int cond_read_bool(struct policydb *p, struct symtab *s, void *fp); -int cond_read_list(struct policydb *p, void *fp); +int cond_read_list(struct policydb *p, struct policy_file *fp); int cond_write_bool(void *key, void *datum, void *ptr); int cond_write_list(struct policydb *p, void *fp);