From patchwork Thu Feb 27 16:02:55 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ondrej Mosnacek X-Patchwork-Id: 11408821 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 5C5A213A4 for ; Thu, 27 Feb 2020 16:03:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 3BC41246A0 for ; Thu, 27 Feb 2020 16:03:10 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="h/rO1qwH" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729842AbgB0QDJ (ORCPT ); Thu, 27 Feb 2020 11:03:09 -0500 Received: from us-smtp-delivery-1.mimecast.com ([205.139.110.120]:32673 "EHLO us-smtp-1.mimecast.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1729153AbgB0QDJ (ORCPT ); Thu, 27 Feb 2020 11:03:09 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582819388; h=from:from:reply-to:subject:subject: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=Hl0zGBH+n27gE0Df1dBcIr3nnNIxDiWCQl++8TVsIoo=; b=h/rO1qwHxaK9hMYnRIu4YYHVHI5exzZJV67FZvgrEbB147QlyUDndZDOea7qSu5Y3n2WYl BBH2gB5OdzyQa6L+W6ErlaTbubUZcmlH72pKggnP30c0KQWh3v8MYiaVI/7qSnkXOUuVqc FxcpmBwJq0hMe9OEG+jVgYB6xJPwtEw= Received: from mail-wr1-f71.google.com (mail-wr1-f71.google.com [209.85.221.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-190-LR6XcntmORiQ0xrvDrlg5Q-1; Thu, 27 Feb 2020 11:03:06 -0500 X-MC-Unique: LR6XcntmORiQ0xrvDrlg5Q-1 Received: by mail-wr1-f71.google.com with SMTP id c6so24126wrm.18 for ; Thu, 27 Feb 2020 08:03:06 -0800 (PST) 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:in-reply-to :references:mime-version:content-transfer-encoding; bh=Hl0zGBH+n27gE0Df1dBcIr3nnNIxDiWCQl++8TVsIoo=; b=fZBLMRUOPcSw8B+nM+2jBWw5zs6Mj1wJ4W4PK5AxWNSkujZ0Rwe92owp5kMIfNKWxh 92etD64Xah9p3VnDecwCCZHxhk0HHwltUviwFsOcOmBSKh7HujJna9grX7bW5XXXvfND rU373vRVlg8lKp+doh+G60kErjcDtmFCsiYp9XHvQ1kfc/g2lvBv40HyIeBCnvu7Q9Jk th5HzJQkRBZZ/hpxiq0Qcpr5jmGHqTSAfFsmz/4XUt3NRfOkuFDajKgMpnr4It+EgM5E 8S3sGqm70xZ+2keJ6lJscfFiv0hoB1anW224t9tseBw4qbrbaPQH04Vx09gX4fxpRsVy 2NRA== X-Gm-Message-State: APjAAAW8TUruAxzgeNluytYpzbI/goY0NN4jKsnVEDGP1HMGTLxHZEw8 vzQywcCZprA5NcKnGsGB1Yxo28JDtkOgJL+xdSW6Ts4AkFnWR+eQurL4JXaKDlY5B3qEMKQ4X5Q EkNxTgR9DJBrewFjKug== X-Received: by 2002:a05:600c:291d:: with SMTP id i29mr202286wmd.39.1582819380924; Thu, 27 Feb 2020 08:03:00 -0800 (PST) X-Google-Smtp-Source: APXvYqxzoaNXpqxTYgYGeSWmf4uNVUQjUCiM/ufjVIt+fYP4pG/T8Mic8YvbPGeHKPs84NdgaiXp+Q== X-Received: by 2002:a05:600c:291d:: with SMTP id i29mr202260wmd.39.1582819380694; Thu, 27 Feb 2020 08:03:00 -0800 (PST) Received: from omos.redhat.com (nat-pool-brq-t.redhat.com. [213.175.37.10]) by smtp.gmail.com with ESMTPSA id d17sm8063456wmb.36.2020.02.27.08.02.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 27 Feb 2020 08:03:00 -0800 (PST) From: Ondrej Mosnacek To: selinux@vger.kernel.org Cc: Stephen Smalley , James Carter Subject: [PATCH 1/3] libsepol: skip unnecessary check in build_type_map() Date: Thu, 27 Feb 2020 17:02:55 +0100 Message-Id: <20200227160257.340737-2-omosnace@redhat.com> X-Mailer: git-send-email 2.24.1 In-Reply-To: <20200227160257.340737-1-omosnace@redhat.com> References: <20200227160257.340737-1-omosnace@redhat.com> MIME-Version: 1.0 Sender: selinux-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org I copy-pasted it from a different part of the code, which had to deal with policydb that isn't final yet. Since we only deal with the final kernel policy here, we can skip the check for the type datum being NULL. Signed-off-by: Ondrej Mosnacek Acked-by: Stephen Smalley --- libsepol/src/optimize.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c index 1e5e97e8..4d835d47 100644 --- a/libsepol/src/optimize.c +++ b/libsepol/src/optimize.c @@ -40,8 +40,7 @@ static ebitmap_t *build_type_map(const policydb_t *p) return NULL; for (i = 0; i < p->p_types.nprim; i++) { - if (p->type_val_to_struct[i] && - p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) { + if (p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) { if (ebitmap_cpy(&map[i], &p->type_attr_map[i])) goto err; } else { From patchwork Thu Feb 27 16:02:56 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ondrej Mosnacek X-Patchwork-Id: 11408819 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BDF5A13A4 for ; Thu, 27 Feb 2020 16:03:08 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 9C94E246A0 for ; Thu, 27 Feb 2020 16:03:08 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="U2THaQV6" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729558AbgB0QDH (ORCPT ); Thu, 27 Feb 2020 11:03:07 -0500 Received: from us-smtp-1.mimecast.com ([207.211.31.81]:29285 "EHLO us-smtp-1.mimecast.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729153AbgB0QDH (ORCPT ); Thu, 27 Feb 2020 11:03:07 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582819385; h=from:from:reply-to:subject:subject: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=y5V5O4Frh8/tdoAgx14UNDt+09hzQ6GHQblCrdvgshk=; b=U2THaQV6groTJMlrg7Y/zryTS5fjZzB6IrFkYipiys/NKmaDtjkjk+7SMEHNEOw68EVxLg 7tQxMq60ovx4IYG5VIRIrDKUgRGyEXrnvg/wCi9JSfHnBQFG1Pim3CPUUI0DrSYs/WzSjY E9nDrjanZUUdDaM5n8JwHl9jUVtK2qA= Received: from mail-wr1-f70.google.com (mail-wr1-f70.google.com [209.85.221.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-13-J3bR5OLePCCejGI8xgm0Zg-1; Thu, 27 Feb 2020 11:03:03 -0500 X-MC-Unique: J3bR5OLePCCejGI8xgm0Zg-1 Received: by mail-wr1-f70.google.com with SMTP id o9so28706wrw.14 for ; Thu, 27 Feb 2020 08:03:02 -0800 (PST) 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:in-reply-to :references:mime-version:content-transfer-encoding; bh=y5V5O4Frh8/tdoAgx14UNDt+09hzQ6GHQblCrdvgshk=; b=P3mLHUCWcn800ewZF8HIOa0dcRsJWVsQ3TfaVW1JGaomnGk5jGYjxNSxzi3nw8ndJd e3PlSReIya/E1DJHzcxl4uRbGuGWzd6AupsXcyv31oO+/vCk2VyH54c8JT9DoFcVOqpZ 38FwrCdWevxImxXvLUFe4hhuB6ESSRBsYThwXZIbm55KacJuFI0nQqUbQjQur8nRSdPR HaqOoDak2V65JyGB+JbwSBLvaQ8nUF5yJpMxf75S9GgTWeviLn3/YhlAZcrcKGNNB/+7 tT36uzBAzXI0lI8t2u2cfQl7HzXyWblW2K7Su8/jQMesM036p+uD25sA3lw2mz9ymeoX rENQ== X-Gm-Message-State: APjAAAVERF+sZlfDy+HDe9yDQo6wzL0J3NFs9BySyc6O1W9Qrb3cy0QE E8PT56fAcaxdazmCvl+1vG/kTt1kGKkv6IAYIduah+h0g/c9jEloBhnyTLrQYQvsOg+EXClT7Y9 7fv5/udKXARGgB2gyLg== X-Received: by 2002:adf:f310:: with SMTP id i16mr5823202wro.326.1582819381746; Thu, 27 Feb 2020 08:03:01 -0800 (PST) X-Google-Smtp-Source: APXvYqyHVrhKV5Pcn1E+9GcBYmThs5tTBv2/mcIFx0fHOPG8USvtFz7WT3UXBBbCGbx5K4YnTRfhKw== X-Received: by 2002:adf:f310:: with SMTP id i16mr5823183wro.326.1582819381560; Thu, 27 Feb 2020 08:03:01 -0800 (PST) Received: from omos.redhat.com (nat-pool-brq-t.redhat.com. [213.175.37.10]) by smtp.gmail.com with ESMTPSA id d17sm8063456wmb.36.2020.02.27.08.03.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 27 Feb 2020 08:03:01 -0800 (PST) From: Ondrej Mosnacek To: selinux@vger.kernel.org Cc: Stephen Smalley , James Carter Subject: [PATCH 2/3] libsepol: optimize inner loop in build_type_map() Date: Thu, 27 Feb 2020 17:02:56 +0100 Message-Id: <20200227160257.340737-3-omosnace@redhat.com> X-Mailer: git-send-email 2.24.1 In-Reply-To: <20200227160257.340737-1-omosnace@redhat.com> References: <20200227160257.340737-1-omosnace@redhat.com> MIME-Version: 1.0 Sender: selinux-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Only attributes can be a superset of another attribute, so we can skip non-attributes right away. Signed-off-by: Ondrej Mosnacek Acked-by: Stephen Smalley --- libsepol/src/optimize.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c index 4d835d47..2b5102af 100644 --- a/libsepol/src/optimize.c +++ b/libsepol/src/optimize.c @@ -50,6 +50,9 @@ static ebitmap_t *build_type_map(const policydb_t *p) for (k = 0; k < p->p_types.nprim; k++) { ebitmap_t *types_k = &p->attr_type_map[k]; + if (p->type_val_to_struct[k]->flavor != TYPE_ATTRIB) + continue; + if (ebitmap_contains(types_k, types_i)) { if (ebitmap_set_bit(&map[i], k, 1)) goto err; From patchwork Thu Feb 27 16:02:57 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ondrej Mosnacek X-Patchwork-Id: 11408823 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 3B0E7930 for ; Thu, 27 Feb 2020 16:03:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 11116246A0 for ; Thu, 27 Feb 2020 16:03:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="NFBq5zOv" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729841AbgB0QDK (ORCPT ); Thu, 27 Feb 2020 11:03:10 -0500 Received: from us-smtp-delivery-1.mimecast.com ([205.139.110.120]:48982 "EHLO us-smtp-1.mimecast.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1729153AbgB0QDK (ORCPT ); Thu, 27 Feb 2020 11:03:10 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582819389; h=from:from:reply-to:subject:subject: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=WMv5VfmQfWfnTudeP8g0DGf9u1ZopZuCiFUiph6aMeE=; b=NFBq5zOvFmEzvxy1u7uax5BpX7poGXGdjegD36qEf4pvtrKTfk3qSq/4x2G4YvVp3Y8jrn 1FYqrZ9obgwz6QdsLFh5mki5UdJMCN+iGGN2T+biheaOqp+yvhQcaaTMBedysTC5NjWCIC 12iAiwNwvY0WfjBsdBhMc6Rli6MDudE= Received: from mail-wm1-f72.google.com (mail-wm1-f72.google.com [209.85.128.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-380-3373vVr9PYq87V3UAejfEQ-1; Thu, 27 Feb 2020 11:03:07 -0500 X-MC-Unique: 3373vVr9PYq87V3UAejfEQ-1 Received: by mail-wm1-f72.google.com with SMTP id t17so862347wmi.7 for ; Thu, 27 Feb 2020 08:03:06 -0800 (PST) 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:in-reply-to :references:mime-version:content-transfer-encoding; bh=WMv5VfmQfWfnTudeP8g0DGf9u1ZopZuCiFUiph6aMeE=; b=MqMGpwUyWTFvbprlvWa23CBxGiD0x45S8YH4Rx+TMXA3icIrRrmDIjIVtryGKt1/9r upC6UhyLju8tFkOco9yqvsDcrdEvxQSwc4btk3OgM9fvb8B8faxjalCDU1h4Gaq36LSW mVQNh2sip7A3gpQ9boyrroGK/TfaC6yT7XGVqvr4QHb0BOLmH2142KGnXNVwJYHN6YCj kfY5AU3mrYtoug6mPtkwLc0kE/VCbLzcBXzI/TYil55BRuggPPyQ+erF9jLDEK5IKDrq Z5xRGw3Jl+9iwW9ouTysBC/Iv7iapPAaQ7FmzI/lDs1Px/vQbPST5GsDH/W6ILEXPwz6 GRPQ== X-Gm-Message-State: APjAAAVjIUqz9NnBgneJ1NYM0dxvmXzLo8nYh1gSCLMI16CdapO9VrxF C4v215DRLocf0EaMcYoWNbqQ50u1FERtNd6hFgA3nm+/CHHLuSM0peM265Yyl5B8mqEw0qRpd2y 2xW5j4Gd7c9/H7YPiRg== X-Received: by 2002:a7b:c416:: with SMTP id k22mr208945wmi.25.1582819383028; Thu, 27 Feb 2020 08:03:03 -0800 (PST) X-Google-Smtp-Source: APXvYqxm3FreARqR+ixYi71A8Sex5YXDTklTk14h6p4+B2AMszyFS1ptCT8edXVk8nacqqzxqW36UQ== X-Received: by 2002:a7b:c416:: with SMTP id k22mr208921wmi.25.1582819382664; Thu, 27 Feb 2020 08:03:02 -0800 (PST) Received: from omos.redhat.com (nat-pool-brq-t.redhat.com. [213.175.37.10]) by smtp.gmail.com with ESMTPSA id d17sm8063456wmb.36.2020.02.27.08.03.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 27 Feb 2020 08:03:01 -0800 (PST) From: Ondrej Mosnacek To: selinux@vger.kernel.org Cc: Stephen Smalley , James Carter Subject: [PATCH 3/3] libsepol: speed up policy optimization Date: Thu, 27 Feb 2020 17:02:57 +0100 Message-Id: <20200227160257.340737-4-omosnace@redhat.com> X-Mailer: git-send-email 2.24.1 In-Reply-To: <20200227160257.340737-1-omosnace@redhat.com> References: <20200227160257.340737-1-omosnace@redhat.com> MIME-Version: 1.0 Sender: selinux-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The iteration over the set ebitmap bits is not implemented very efficiently in libsepol. It is slowing down the policy optimization quite significantly, so convert the type_map from an array of ebitmaps to an array of simple ordered vectors, which can be traveresed more easily. The worse space efficiency of the vectors is less important than the speed in this case. After this change the duration of semodule -BN decreased from 6.4s to 5.5s on Fedora Rawhide x86_64 (and from 6.1s to 5.6s with the unconfined module disabled). Signed-off-by: Ondrej Mosnacek Acked-by: Stephen Smalley --- libsepol/src/optimize.c | 113 ++++++++++++++++++++++++++++++++-------- 1 file changed, 90 insertions(+), 23 deletions(-) diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c index 2b5102af..6826155c 100644 --- a/libsepol/src/optimize.c +++ b/libsepol/src/optimize.c @@ -31,22 +31,85 @@ #include #include +#define TYPE_VEC_INIT_SIZE 16 + +struct type_vec { + uint32_t *types; + unsigned int count, capacity; +}; + +static int type_vec_init(struct type_vec *v) +{ + v->capacity = TYPE_VEC_INIT_SIZE; + v->count = 0; + v->types = malloc(v->capacity * sizeof(*v->types)); + if (!v->types) + return -1; + return 0; +} + +static void type_vec_destroy(struct type_vec *v) +{ + free(v->types); +} + +static int type_vec_append(struct type_vec *v, uint32_t type) +{ + if (v->capacity == v->count) { + unsigned int new_capacity = v->capacity * 2; + uint32_t *new_types = realloc(v->types, + new_capacity * sizeof(*v->types)); + if (!new_types) + return -1; + + v->types = new_types; + v->capacity = new_capacity; + } + + v->types[v->count++] = type; + return 0; +} + +static int type_vec_contains(const struct type_vec *v, uint32_t type) +{ + unsigned int s = 0, e = v->count; + + while (s != e) { + unsigned int mid = (s + e) / 2; + + if (v->types[mid] == type) + return 1; + + if (v->types[mid] < type) + s = mid + 1; + else + e = mid; + } + return 0; +} + /* builds map: type/attribute -> {all attributes that are a superset of it} */ -static ebitmap_t *build_type_map(const policydb_t *p) +static struct type_vec *build_type_map(const policydb_t *p) { unsigned int i, k; - ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t)); + ebitmap_node_t *n; + struct type_vec *map = malloc(p->p_types.nprim * sizeof(*map)); if (!map) return NULL; for (i = 0; i < p->p_types.nprim; i++) { + if (type_vec_init(&map[i])) + goto err; + if (p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) { - if (ebitmap_cpy(&map[i], &p->type_attr_map[i])) - goto err; + ebitmap_for_each_positive_bit(&p->type_attr_map[i], + n, k) { + if (type_vec_append(&map[i], k)) + goto err; + } } else { ebitmap_t *types_i = &p->attr_type_map[i]; - ebitmap_init(&map[i]); for (k = 0; k < p->p_types.nprim; k++) { ebitmap_t *types_k = &p->attr_type_map[k]; @@ -54,7 +117,7 @@ static ebitmap_t *build_type_map(const policydb_t *p) continue; if (ebitmap_contains(types_k, types_i)) { - if (ebitmap_set_bit(&map[i], k, 1)) + if (type_vec_append(&map[i], k)) goto err; } } @@ -63,16 +126,16 @@ static ebitmap_t *build_type_map(const policydb_t *p) return map; err: for (k = 0; k <= i; k++) - ebitmap_destroy(&map[k]); + type_vec_destroy(&map[k]); free(map); return NULL; } -static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map) +static void destroy_type_map(const policydb_t *p, struct type_vec *type_map) { unsigned int i; for (i = 0; i < p->p_types.nprim; i++) - ebitmap_destroy(&type_map[i]); + type_vec_destroy(&type_map[i]); free(type_map); } @@ -125,10 +188,11 @@ static int process_avtab_datum(uint16_t specified, /* checks if avtab contains a rule that covers the given rule */ static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab, - const ebitmap_t *type_map, unsigned char not_cond) + const struct type_vec *type_map, + unsigned char not_cond) { unsigned int i, k, s_idx, t_idx; - ebitmap_node_t *snode, *tnode; + uint32_t st, tt; avtab_datum_t *d1, *d2; avtab_key_t key; @@ -144,14 +208,17 @@ static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab, d1 = &entry->datum; - ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) { - key.source_type = i + 1; + for (i = 0; i < type_map[s_idx].count; i++) { + st = type_map[s_idx].types[i]; + key.source_type = st + 1; + + for (k = 0; k < type_map[t_idx].count; k++) { + tt = type_map[t_idx].types[k]; - ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) { - if (not_cond && s_idx == i && t_idx == k) + if (not_cond && s_idx == st && t_idx == tt) continue; - key.target_type = k + 1; + key.target_type = tt + 1; d2 = avtab_search(tab, &key); if (!d2) @@ -179,7 +246,7 @@ static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p) /* checks if conditional list contains a rule that covers the given rule */ static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list, - const ebitmap_t *type_map) + const struct type_vec *type_map) { unsigned int s1, t1, c1, k1, s2, t2, c2, k2; @@ -205,9 +272,9 @@ static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list, if (s1 == s2 && t1 == t2) continue; - if (!ebitmap_get_bit(&type_map[s1], s2)) + if (!type_vec_contains(&type_map[s1], s2)) continue; - if (!ebitmap_get_bit(&type_map[t1], t2)) + if (!type_vec_contains(&type_map[t1], t2)) continue; if (process_avtab_datum(k1, &e1->datum, &e2->datum)) @@ -216,7 +283,7 @@ static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list, return 0; } -static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map) +static void optimize_avtab(policydb_t *p, const struct type_vec *type_map) { avtab_t *tab = &p->te_avtab; unsigned int i; @@ -245,7 +312,7 @@ static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map) /* find redundant rules in (*cond) and put them into (*del) */ static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del, - policydb_t *p, const ebitmap_t *type_map) + policydb_t *p, const struct type_vec *type_map) { cond_av_list_t **listp = cond; cond_av_list_t *pcov = NULL; @@ -294,7 +361,7 @@ static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del, } } -static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map) +static void optimize_cond_avtab(policydb_t *p, const struct type_vec *type_map) { avtab_t *tab = &p->te_cond_avtab; unsigned int i; @@ -363,7 +430,7 @@ static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map) int policydb_optimize(policydb_t *p) { - ebitmap_t *type_map; + struct type_vec *type_map; if (p->policy_type != POLICY_KERN) return -1;