From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.1 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI, SIGNED_OFF_BY,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 474ACC282C2 for ; Thu, 7 Feb 2019 11:23:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D5A6021902 for ; Thu, 7 Feb 2019 11:23:15 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=Mellanox.com header.i=@Mellanox.com header.b="qoqINEmh" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727074AbfBGLXO (ORCPT ); Thu, 7 Feb 2019 06:23:14 -0500 Received: from mail-eopbgr30058.outbound.protection.outlook.com ([40.107.3.58]:15520 "EHLO EUR03-AM5-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1726727AbfBGLXK (ORCPT ); Thu, 7 Feb 2019 06:23:10 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Mellanox.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=vD5nylUc/GixcmRHVnKRiptDYiB7ivKX0e96ea84ohY=; b=qoqINEmhrUImd/rpH9sa21wNF/5B8g86L6haseQDb0EVE1aFd2oLpa78i9kGzsBz/812YT803gNL7YhwxN6IO3sBFOd7OIDB+jg/D0zgjqIGS6bEnXAuhj351rH5zqe/T9Dc7vZVj5fzH/pHB1sJc279W1BA2CXU9St1pFkAsEc= Received: from AM6PR05MB5240.eurprd05.prod.outlook.com (20.177.196.214) by AM6PR05MB5624.eurprd05.prod.outlook.com (20.178.86.25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1601.21; Thu, 7 Feb 2019 11:22:46 +0000 Received: from AM6PR05MB5240.eurprd05.prod.outlook.com ([fe80::3542:889c:3a85:3866]) by AM6PR05MB5240.eurprd05.prod.outlook.com ([fe80::3542:889c:3a85:3866%5]) with mapi id 15.20.1601.016; Thu, 7 Feb 2019 11:22:46 +0000 From: Ido Schimmel To: "netdev@vger.kernel.org" CC: "davem@davemloft.net" , Jiri Pirko , mlxsw , Ido Schimmel Subject: [PATCH net-next 02/14] lib: objagg: implement optimization hints assembly and use hints for object creation Thread-Topic: [PATCH net-next 02/14] lib: objagg: implement optimization hints assembly and use hints for object creation Thread-Index: AQHUvtdzAqLN1jZ2mE+/cl4j5aalyQ== Date: Thu, 7 Feb 2019 11:22:46 +0000 Message-ID: <20190207112211.10375-3-idosch@mellanox.com> References: <20190207112211.10375-1-idosch@mellanox.com> In-Reply-To: <20190207112211.10375-1-idosch@mellanox.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-clientproxiedby: AM6P194CA0032.EURP194.PROD.OUTLOOK.COM (2603:10a6:209:90::45) To AM6PR05MB5240.eurprd05.prod.outlook.com (2603:10a6:20b:64::22) authentication-results: spf=none (sender IP is ) smtp.mailfrom=idosch@mellanox.com; x-ms-exchange-messagesentrepresentingtype: 1 x-mailer: git-send-email 2.20.1 x-originating-ip: [193.47.165.251] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;AM6PR05MB5624;6:uvGgFHe6rQVhhKz/bXc1NE30G5q84CvrU6kN+rl2vNYEvR3l5qxv9yMpWyxYTcX+gx08Chb8sQc1rX/tA/56YqiCz8xjphhXV9lx3gBUdfn7jt/mLujaDccmcQq2Grq6Cxdt5k2EK3GgP/wYvMz9jnUzZ4iFzrDNmlzpHbfCykU6zuRhyOY+FwEBlVBQq0TDM/JUocKH38tK1HjDumrZMAitpoZk/ey5S23I7laqV7KCwZ4S8vcjMA91iZr9DIvU6CADYWMSIHB5unUA9HF/3FvLRFF4jUUR42J44Jhhij+G4kOJulejdtO9QGHnbqn39I5u2xT+HkEcOCpA68Fqi4ALLfb5HVpPgEuF4BGmO0UPDZ0QfwdylP9Mwd8ZHwRcoo+nQYbER7ehOmhh88aaqxvhfAOHQopX5lK2jU/pC+6SMMdVZ0z/wzLKHNddZYnDdipm//w8DNVRnciuX108iw==;5:bE/UVQzdu//cOUNc45m/PtFv4YtEQSZDw68PjkN+dDuMmaqIT7HRU605JoBX1OfLwYmnJwjwjq0HZsTt9WFs0AK68IKDAsXU7jguXDz1C6pyCYoVfNhsv9KblIfy4/ZzScYyRbBGGVUvyO0r8LDGwPXyt94BaG+SW7WNn1Nz+/uA2LbjVsDOH7hoLBn4Eo26GZWze+pxwctZxysoCDSOqg==;7:0bIFgcaLzdAQa3P2UDto5zwAd680K6A0jCNv8F4uq5GdBVsNOo8eDh4+Pul8laaORBz/8fdxmYTG7/IgBNG6aNyRmPO5Rp91lNDh4F1hSbUBlUwQieFDSwE7WhTqmkwfizwH+/z3lZzIc9OnyoCsCQ== x-ms-office365-filtering-correlation-id: 2cad0a20-d3c2-4613-544d-08d68cee956b x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0;PCL:0;RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600110)(711020)(4605077)(4618075)(2017052603328)(7153060)(7193020);SRVR:AM6PR05MB5624; x-ms-traffictypediagnostic: AM6PR05MB5624: x-microsoft-antispam-prvs: x-forefront-prvs: 0941B96580 x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(376002)(346002)(396003)(136003)(366004)(39860400002)(189003)(199004)(81166006)(81156014)(8676002)(68736007)(8936002)(66066001)(6916009)(105586002)(3846002)(6116002)(71200400001)(71190400001)(6506007)(386003)(1076003)(102836004)(2351001)(478600001)(36756003)(52116002)(30864003)(2501003)(14454004)(76176011)(106356001)(26005)(1730700003)(50226002)(305945005)(186003)(54906003)(4326008)(2616005)(6512007)(6486002)(7736002)(53946003)(446003)(53936002)(107886003)(6436002)(256004)(14444005)(99286004)(11346002)(5640700003)(316002)(86362001)(476003)(2906002)(486006)(97736004)(25786009)(569006);DIR:OUT;SFP:1101;SCL:1;SRVR:AM6PR05MB5624;H:AM6PR05MB5240.eurprd05.prod.outlook.com;FPR:;SPF:None;LANG:en;PTR:InfoNoRecords;MX:1;A:1; received-spf: None (protection.outlook.com: mellanox.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: LiLjlDuF2nJhbGROg+aKIWZymcYz4jHwdSu9jABjnKiFKtWOqGf6VmlgebpPESZzD1dOKqZPJz9EJpBj9pffaZdZ4t6+K+bqRSwLI2jZaE+yus7egzk6OJNgIs7FW86pyYh6I5FiDHqYg8hHnLPmw3ksmCJiVeppcWuXhMDwFfWuYQcIKn/v3mUdLfH3QloMpY20REHq6+vOpSll0x3/a7cbcS9eI/jDvo3egurn9MR6aGSFm75k85ot74iQTixLqda5CSV7vghWYrw5/h+vYeMXI8R109krL9BeZOp4zz73eyu+pfzNeVHxW6S5TUEmxuX4aD9pNiXvxZd4ULbdzFnbcaus3PM8mpWjeaRVsypm9R4xrbfWg9MxuIy4WUxeyLxr3q5AcEYc5dOpv36thmcypRWtWDxbCznIvo3bHuI= Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: Mellanox.com X-MS-Exchange-CrossTenant-Network-Message-Id: 2cad0a20-d3c2-4613-544d-08d68cee956b X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Feb 2019 11:22:45.1984 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-id: a652971c-7d2e-4d9b-a6a4-d149256f461b X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR05MB5624 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiri Pirko Implement simple greedy algo to find more optimized root-delta tree for a given objagg instance. This "hints" can be used by a driver to: 1) check if the hints are better (driver's choice) than the original objagg tree. Driver does comparison of objagg stats and hints stats. 2) use the hints to create a new objagg instance which will construct the root-delta tree according to the passed hints. Currently, only a simple greedy algorithm is implemented. Basically it finds the roots according to the maximal possible user count including deltas. Signed-off-by: Jiri Pirko Signed-off-by: Ido Schimmel --- .../mellanox/mlxsw/spectrum_acl_erp.c | 37 +- include/linux/objagg.h | 20 +- lib/objagg.c | 573 +++++++++++++++++- lib/test_objagg.c | 194 +++++- 4 files changed, 802 insertions(+), 22 deletions(-) diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c b/drive= rs/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c index 2941967e1cc5..302070a74f2e 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c @@ -1200,6 +1200,32 @@ mlxsw_sp_acl_erp_delta_fill(const struct mlxsw_sp_ac= l_erp_key *parent_key, return 0; } =20 +static bool mlxsw_sp_acl_erp_delta_check(void *priv, const void *parent_ob= j, + const void *obj) +{ + const struct mlxsw_sp_acl_erp_key *parent_key =3D parent_obj; + const struct mlxsw_sp_acl_erp_key *key =3D obj; + u16 delta_start; + u8 delta_mask; + int err; + + err =3D mlxsw_sp_acl_erp_delta_fill(parent_key, key, + &delta_start, &delta_mask); + return err ? false : true; +} + +static int mlxsw_sp_acl_erp_hints_obj_cmp(const void *obj1, const void *ob= j2) +{ + const struct mlxsw_sp_acl_erp_key *key1 =3D obj1; + const struct mlxsw_sp_acl_erp_key *key2 =3D obj2; + + /* For hints purposes, two objects are considered equal + * in case the masks are the same. Does not matter what + * the "ctcam" value is. + */ + return memcmp(key1->mask, key2->mask, sizeof(key1->mask)); +} + static void *mlxsw_sp_acl_erp_delta_create(void *priv, void *parent_obj, void *obj) { @@ -1254,12 +1280,17 @@ static void mlxsw_sp_acl_erp_delta_destroy(void *pr= iv, void *delta_priv) kfree(delta); } =20 -static void *mlxsw_sp_acl_erp_root_create(void *priv, void *obj) +static void *mlxsw_sp_acl_erp_root_create(void *priv, void *obj, + unsigned int root_id) { struct mlxsw_sp_acl_atcam_region *aregion =3D priv; struct mlxsw_sp_acl_erp_table *erp_table =3D aregion->erp_table; struct mlxsw_sp_acl_erp_key *key =3D obj; =20 + if (!key->ctcam && + root_id !=3D OBJAGG_OBJ_ROOT_ID_INVALID && + root_id >=3D MLXSW_SP_ACL_ERP_MAX_PER_REGION) + return ERR_PTR(-ENOBUFS); return erp_table->ops->erp_create(erp_table, key); } =20 @@ -1273,6 +1304,8 @@ static void mlxsw_sp_acl_erp_root_destroy(void *priv,= void *root_priv) =20 static const struct objagg_ops mlxsw_sp_acl_erp_objagg_ops =3D { .obj_size =3D sizeof(struct mlxsw_sp_acl_erp_key), + .delta_check =3D mlxsw_sp_acl_erp_delta_check, + .hints_obj_cmp =3D mlxsw_sp_acl_erp_hints_obj_cmp, .delta_create =3D mlxsw_sp_acl_erp_delta_create, .delta_destroy =3D mlxsw_sp_acl_erp_delta_destroy, .root_create =3D mlxsw_sp_acl_erp_root_create, @@ -1290,7 +1323,7 @@ mlxsw_sp_acl_erp_table_create(struct mlxsw_sp_acl_atc= am_region *aregion) return ERR_PTR(-ENOMEM); =20 erp_table->objagg =3D objagg_create(&mlxsw_sp_acl_erp_objagg_ops, - aregion); + NULL, aregion); if (IS_ERR(erp_table->objagg)) { err =3D PTR_ERR(erp_table->objagg); goto err_objagg_create; diff --git a/include/linux/objagg.h b/include/linux/objagg.h index 34f38c186ea0..a675286df1af 100644 --- a/include/linux/objagg.h +++ b/include/linux/objagg.h @@ -6,14 +6,19 @@ =20 struct objagg_ops { size_t obj_size; + bool (*delta_check)(void *priv, const void *parent_obj, + const void *obj); + int (*hints_obj_cmp)(const void *obj1, const void *obj2); void * (*delta_create)(void *priv, void *parent_obj, void *obj); void (*delta_destroy)(void *priv, void *delta_priv); - void * (*root_create)(void *priv, void *obj); + void * (*root_create)(void *priv, void *obj, unsigned int root_id); +#define OBJAGG_OBJ_ROOT_ID_INVALID UINT_MAX void (*root_destroy)(void *priv, void *root_priv); }; =20 struct objagg; struct objagg_obj; +struct objagg_hints; =20 const void *objagg_obj_root_priv(const struct objagg_obj *objagg_obj); const void *objagg_obj_delta_priv(const struct objagg_obj *objagg_obj); @@ -21,7 +26,8 @@ const void *objagg_obj_raw(const struct objagg_obj *objag= g_obj); =20 struct objagg_obj *objagg_obj_get(struct objagg *objagg, void *obj); void objagg_obj_put(struct objagg *objagg, struct objagg_obj *objagg_obj); -struct objagg *objagg_create(const struct objagg_ops *ops, void *priv); +struct objagg *objagg_create(const struct objagg_ops *ops, + struct objagg_hints *hints, void *priv); void objagg_destroy(struct objagg *objagg); =20 struct objagg_obj_stats { @@ -43,4 +49,14 @@ struct objagg_stats { const struct objagg_stats *objagg_stats_get(struct objagg *objagg); void objagg_stats_put(const struct objagg_stats *objagg_stats); =20 +enum objagg_opt_algo_type { + OBJAGG_OPT_ALGO_SIMPLE_GREEDY, +}; + +struct objagg_hints *objagg_hints_get(struct objagg *objagg, + enum objagg_opt_algo_type opt_algo_type); +void objagg_hints_put(struct objagg_hints *objagg_hints); +const struct objagg_stats * +objagg_hints_stats_get(struct objagg_hints *objagg_hints); + #endif diff --git a/lib/objagg.c b/lib/objagg.c index c9b457a91153..94c9fa7acc5a 100644 --- a/lib/objagg.c +++ b/lib/objagg.c @@ -4,6 +4,7 @@ #include #include #include +#include #include #include #include @@ -11,6 +12,34 @@ #define CREATE_TRACE_POINTS #include =20 +struct objagg_hints { + struct rhashtable node_ht; + struct rhashtable_params ht_params; + struct list_head node_list; + unsigned int node_count; + unsigned int root_count; + unsigned int refcount; + const struct objagg_ops *ops; +}; + +struct objagg_hints_node { + struct rhash_head ht_node; /* member of objagg_hints->node_ht */ + struct list_head list; /* member of objagg_hints->node_list */ + struct objagg_hints_node *parent; + unsigned int root_id; + struct objagg_obj_stats_info stats_info; + unsigned long obj[0]; +}; + +static struct objagg_hints_node * +objagg_hints_lookup(struct objagg_hints *objagg_hints, void *obj) +{ + if (!objagg_hints) + return NULL; + return rhashtable_lookup_fast(&objagg_hints->node_ht, obj, + objagg_hints->ht_params); +} + struct objagg { const struct objagg_ops *ops; void *priv; @@ -18,6 +47,8 @@ struct objagg { struct rhashtable_params ht_params; struct list_head obj_list; unsigned int obj_count; + struct ida root_ida; + struct objagg_hints *hints; }; =20 struct objagg_obj { @@ -30,6 +61,7 @@ struct objagg_obj { void *delta_priv; /* user delta private */ void *root_priv; /* user root private */ }; + unsigned int root_id; unsigned int refcount; /* counts number of users of this object * including nested objects */ @@ -130,7 +162,8 @@ static struct objagg_obj *objagg_obj_lookup(struct obja= gg *objagg, void *obj) =20 static int objagg_obj_parent_assign(struct objagg *objagg, struct objagg_obj *objagg_obj, - struct objagg_obj *parent) + struct objagg_obj *parent, + bool take_parent_ref) { void *delta_priv; =20 @@ -144,7 +177,8 @@ static int objagg_obj_parent_assign(struct objagg *obja= gg, */ objagg_obj->parent =3D parent; objagg_obj->delta_priv =3D delta_priv; - objagg_obj_ref_inc(objagg_obj->parent); + if (take_parent_ref) + objagg_obj_ref_inc(objagg_obj->parent); trace_objagg_obj_parent_assign(objagg, objagg_obj, parent, parent->refcount); @@ -164,7 +198,7 @@ static int objagg_obj_parent_lookup_assign(struct objag= g *objagg, if (!objagg_obj_is_root(objagg_obj_cur)) continue; err =3D objagg_obj_parent_assign(objagg, objagg_obj, - objagg_obj_cur); + objagg_obj_cur, true); if (!err) return 0; } @@ -184,16 +218,68 @@ static void objagg_obj_parent_unassign(struct objagg = *objagg, __objagg_obj_put(objagg, objagg_obj->parent); } =20 +static int objagg_obj_root_id_alloc(struct objagg *objagg, + struct objagg_obj *objagg_obj, + struct objagg_hints_node *hnode) +{ + unsigned int min, max; + int root_id; + + /* In case there are no hints available, the root id is invalid. */ + if (!objagg->hints) { + objagg_obj->root_id =3D OBJAGG_OBJ_ROOT_ID_INVALID; + return 0; + } + + if (hnode) { + min =3D hnode->root_id; + max =3D hnode->root_id; + } else { + /* For objects with no hint, start after the last + * hinted root_id. + */ + min =3D objagg->hints->root_count; + max =3D ~0; + } + + root_id =3D ida_alloc_range(&objagg->root_ida, min, max, GFP_KERNEL); + + if (root_id < 0) + return root_id; + objagg_obj->root_id =3D root_id; + return 0; +} + +static void objagg_obj_root_id_free(struct objagg *objagg, + struct objagg_obj *objagg_obj) +{ + if (!objagg->hints) + return; + ida_free(&objagg->root_ida, objagg_obj->root_id); +} + static int objagg_obj_root_create(struct objagg *objagg, - struct objagg_obj *objagg_obj) + struct objagg_obj *objagg_obj, + struct objagg_hints_node *hnode) { - objagg_obj->root_priv =3D objagg->ops->root_create(objagg->priv, - objagg_obj->obj); - if (IS_ERR(objagg_obj->root_priv)) - return PTR_ERR(objagg_obj->root_priv); + int err; =20 + err =3D objagg_obj_root_id_alloc(objagg, objagg_obj, hnode); + if (err) + return err; + objagg_obj->root_priv =3D objagg->ops->root_create(objagg->priv, + objagg_obj->obj, + objagg_obj->root_id); + if (IS_ERR(objagg_obj->root_priv)) { + err =3D PTR_ERR(objagg_obj->root_priv); + goto err_root_create; + } trace_objagg_obj_root_create(objagg, objagg_obj); return 0; + +err_root_create: + objagg_obj_root_id_free(objagg, objagg_obj); + return err; } =20 static void objagg_obj_root_destroy(struct objagg *objagg, @@ -201,19 +287,69 @@ static void objagg_obj_root_destroy(struct objagg *ob= jagg, { trace_objagg_obj_root_destroy(objagg, objagg_obj); objagg->ops->root_destroy(objagg->priv, objagg_obj->root_priv); + objagg_obj_root_id_free(objagg, objagg_obj); +} + +static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *ob= j); + +static int objagg_obj_init_with_hints(struct objagg *objagg, + struct objagg_obj *objagg_obj, + bool *hint_found) +{ + struct objagg_hints_node *hnode; + struct objagg_obj *parent; + int err; + + hnode =3D objagg_hints_lookup(objagg->hints, objagg_obj->obj); + if (!hnode) { + *hint_found =3D false; + return 0; + } + *hint_found =3D true; + + if (!hnode->parent) + return objagg_obj_root_create(objagg, objagg_obj, hnode); + + parent =3D __objagg_obj_get(objagg, hnode->parent->obj); + if (IS_ERR(parent)) + return PTR_ERR(parent); + + err =3D objagg_obj_parent_assign(objagg, objagg_obj, parent, false); + if (err) { + *hint_found =3D false; + err =3D 0; + goto err_parent_assign; + } + + return 0; + +err_parent_assign: + objagg_obj_put(objagg, parent); + return err; } =20 static int objagg_obj_init(struct objagg *objagg, struct objagg_obj *objagg_obj) { + bool hint_found; int err; =20 + /* First, try to use hints if they are available and + * if they provide result. + */ + err =3D objagg_obj_init_with_hints(objagg, objagg_obj, &hint_found); + if (err) + return err; + + if (hint_found) + return 0; + /* Try to find if the object can be aggregated under an existing one. */ err =3D objagg_obj_parent_lookup_assign(objagg, objagg_obj); if (!err) return 0; /* If aggregation is not possible, make the object a root. */ - return objagg_obj_root_create(objagg, objagg_obj); + return objagg_obj_root_create(objagg, objagg_obj, NULL); } =20 static void objagg_obj_fini(struct objagg *objagg, @@ -349,8 +485,9 @@ EXPORT_SYMBOL(objagg_obj_put); =20 /** * objagg_create - creates a new objagg instance - * @ops: user-specific callbacks - * @priv: pointer to a private data passed to the ops + * @ops: user-specific callbacks + * @objagg_hints: hints, can be NULL + * @priv: pointer to a private data passed to the ops * * Note: all locking must be provided by the caller. * @@ -374,18 +511,25 @@ EXPORT_SYMBOL(objagg_obj_put); * Returns a pointer to newly created objagg instance in case of success, * otherwise it returns pointer error using ERR_PTR macro. */ -struct objagg *objagg_create(const struct objagg_ops *ops, void *priv) +struct objagg *objagg_create(const struct objagg_ops *ops, + struct objagg_hints *objagg_hints, void *priv) { struct objagg *objagg; int err; =20 if (WARN_ON(!ops || !ops->root_create || !ops->root_destroy || - !ops->delta_create || !ops->delta_destroy)) + !ops->delta_check || !ops->delta_create || + !ops->delta_destroy)) return ERR_PTR(-EINVAL); + objagg =3D kzalloc(sizeof(*objagg), GFP_KERNEL); if (!objagg) return ERR_PTR(-ENOMEM); objagg->ops =3D ops; + if (objagg_hints) { + objagg->hints =3D objagg_hints; + objagg_hints->refcount++; + } objagg->priv =3D priv; INIT_LIST_HEAD(&objagg->obj_list); =20 @@ -397,6 +541,8 @@ struct objagg *objagg_create(const struct objagg_ops *o= ps, void *priv) if (err) goto err_rhashtable_init; =20 + ida_init(&objagg->root_ida); + trace_objagg_create(objagg); return objagg; =20 @@ -415,8 +561,11 @@ EXPORT_SYMBOL(objagg_create); void objagg_destroy(struct objagg *objagg) { trace_objagg_destroy(objagg); + ida_destroy(&objagg->root_ida); WARN_ON(!list_empty(&objagg->obj_list)); rhashtable_destroy(&objagg->obj_ht); + if (objagg->hints) + objagg_hints_put(objagg->hints); kfree(objagg); } EXPORT_SYMBOL(objagg_destroy); @@ -496,6 +645,404 @@ void objagg_stats_put(const struct objagg_stats *obja= gg_stats) } EXPORT_SYMBOL(objagg_stats_put); =20 +static struct objagg_hints_node * +objagg_hints_node_create(struct objagg_hints *objagg_hints, + struct objagg_obj *objagg_obj, size_t obj_size, + struct objagg_hints_node *parent_hnode) +{ + unsigned int user_count =3D objagg_obj->stats.user_count; + struct objagg_hints_node *hnode; + int err; + + hnode =3D kzalloc(sizeof(*hnode) + obj_size, GFP_KERNEL); + if (!hnode) + return ERR_PTR(-ENOMEM); + memcpy(hnode->obj, &objagg_obj->obj, obj_size); + hnode->stats_info.stats.user_count =3D user_count; + hnode->stats_info.stats.delta_user_count =3D user_count; + if (parent_hnode) { + parent_hnode->stats_info.stats.delta_user_count +=3D user_count; + } else { + hnode->root_id =3D objagg_hints->root_count++; + hnode->stats_info.is_root =3D true; + } + hnode->stats_info.objagg_obj =3D objagg_obj; + + err =3D rhashtable_insert_fast(&objagg_hints->node_ht, &hnode->ht_node, + objagg_hints->ht_params); + if (err) + goto err_ht_insert; + + list_add(&hnode->list, &objagg_hints->node_list); + hnode->parent =3D parent_hnode; + objagg_hints->node_count++; + + return hnode; + +err_ht_insert: + kfree(hnode); + return ERR_PTR(err); +} + +static void objagg_hints_flush(struct objagg_hints *objagg_hints) +{ + struct objagg_hints_node *hnode, *tmp; + + list_for_each_entry_safe(hnode, tmp, &objagg_hints->node_list, list) { + list_del(&hnode->list); + rhashtable_remove_fast(&objagg_hints->node_ht, &hnode->ht_node, + objagg_hints->ht_params); + kfree(hnode); + } +} + +struct objagg_tmp_node { + struct objagg_obj *objagg_obj; + bool crossed_out; +}; + +struct objagg_tmp_graph { + struct objagg_tmp_node *nodes; + unsigned long nodes_count; + unsigned long *edges; +}; + +static int objagg_tmp_graph_edge_index(struct objagg_tmp_graph *graph, + int parent_index, int index) +{ + return index * graph->nodes_count + parent_index; +} + +static void objagg_tmp_graph_edge_set(struct objagg_tmp_graph *graph, + int parent_index, int index) +{ + int edge_index =3D objagg_tmp_graph_edge_index(graph, index, + parent_index); + + __set_bit(edge_index, graph->edges); +} + +static bool objagg_tmp_graph_is_edge(struct objagg_tmp_graph *graph, + int parent_index, int index) +{ + int edge_index =3D objagg_tmp_graph_edge_index(graph, index, + parent_index); + + return test_bit(edge_index, graph->edges); +} + +static unsigned int objagg_tmp_graph_node_weight(struct objagg_tmp_graph *= graph, + unsigned int index) +{ + struct objagg_tmp_node *node =3D &graph->nodes[index]; + unsigned int weight =3D node->objagg_obj->stats.user_count; + int j; + + /* Node weight is sum of node users and all other nodes users + * that this node can represent with delta. + */ + + if (node->crossed_out) + return 0; + for (j =3D 0; j < graph->nodes_count; j++) { + if (!objagg_tmp_graph_is_edge(graph, index, j)) + continue; + node =3D &graph->nodes[j]; + if (node->crossed_out) + continue; + weight +=3D node->objagg_obj->stats.user_count; + } + return weight; +} + +static int objagg_tmp_graph_node_max_weight(struct objagg_tmp_graph *graph= ) +{ + unsigned int max_weight =3D 0; + unsigned int weight; + int max_index =3D -1; + int i; + + for (i =3D 0; i < graph->nodes_count; i++) { + weight =3D objagg_tmp_graph_node_weight(graph, i); + if (weight > max_weight) { + max_weight =3D weight; + max_index =3D i; + } + } + return max_index; +} + +static struct objagg_tmp_graph *objagg_tmp_graph_create(struct objagg *obj= agg) +{ + unsigned int nodes_count =3D objagg->obj_count; + struct objagg_tmp_graph *graph; + struct objagg_tmp_node *node; + struct objagg_tmp_node *pnode; + struct objagg_obj *objagg_obj; + size_t alloc_size; + int i, j; + + graph =3D kzalloc(sizeof(*graph), GFP_KERNEL); + if (!graph) + return NULL; + + graph->nodes =3D kcalloc(nodes_count, sizeof(*graph->nodes), GFP_KERNEL); + if (!graph->nodes) + goto err_nodes_alloc; + graph->nodes_count =3D nodes_count; + + alloc_size =3D BITS_TO_LONGS(nodes_count * nodes_count) * + sizeof(unsigned long); + graph->edges =3D kzalloc(alloc_size, GFP_KERNEL); + if (!graph->edges) + goto err_edges_alloc; + + i =3D 0; + list_for_each_entry(objagg_obj, &objagg->obj_list, list) { + node =3D &graph->nodes[i++]; + node->objagg_obj =3D objagg_obj; + } + + /* Assemble a temporary graph. Insert edge X->Y in case Y can be + * in delta of X. + */ + for (i =3D 0; i < nodes_count; i++) { + for (j =3D 0; j < nodes_count; j++) { + if (i =3D=3D j) + continue; + pnode =3D &graph->nodes[i]; + node =3D &graph->nodes[j]; + if (objagg->ops->delta_check(objagg->priv, + pnode->objagg_obj->obj, + node->objagg_obj->obj)) { + objagg_tmp_graph_edge_set(graph, i, j); + + } + } + } + return graph; + +err_edges_alloc: + kfree(graph->nodes); +err_nodes_alloc: + kfree(graph); + return NULL; +} + +static void objagg_tmp_graph_destroy(struct objagg_tmp_graph *graph) +{ + kfree(graph->edges); + kfree(graph->nodes); + kfree(graph); +} + +static int +objagg_opt_simple_greedy_fillup_hints(struct objagg_hints *objagg_hints, + struct objagg *objagg) +{ + struct objagg_hints_node *hnode, *parent_hnode; + struct objagg_tmp_graph *graph; + struct objagg_tmp_node *node; + int index; + int j; + int err; + + graph =3D objagg_tmp_graph_create(objagg); + if (!graph) + return -ENOMEM; + + /* Find the nodes from the ones that can accommodate most users + * and cross them out of the graph. Save them to the hint list. + */ + while ((index =3D objagg_tmp_graph_node_max_weight(graph)) !=3D -1) { + node =3D &graph->nodes[index]; + node->crossed_out =3D true; + hnode =3D objagg_hints_node_create(objagg_hints, + node->objagg_obj, + objagg->ops->obj_size, + NULL); + if (IS_ERR(hnode)) { + err =3D PTR_ERR(hnode); + goto out; + } + parent_hnode =3D hnode; + for (j =3D 0; j < graph->nodes_count; j++) { + if (!objagg_tmp_graph_is_edge(graph, index, j)) + continue; + node =3D &graph->nodes[j]; + if (node->crossed_out) + continue; + node->crossed_out =3D true; + hnode =3D objagg_hints_node_create(objagg_hints, + node->objagg_obj, + objagg->ops->obj_size, + parent_hnode); + if (IS_ERR(hnode)) { + err =3D PTR_ERR(hnode); + goto out; + } + } + } + + err =3D 0; +out: + objagg_tmp_graph_destroy(graph); + return err; +} + +struct objagg_opt_algo { + int (*fillup_hints)(struct objagg_hints *objagg_hints, + struct objagg *objagg); +}; + +static const struct objagg_opt_algo objagg_opt_simple_greedy =3D { + .fillup_hints =3D objagg_opt_simple_greedy_fillup_hints, +}; + + +static const struct objagg_opt_algo *objagg_opt_algos[] =3D { + [OBJAGG_OPT_ALGO_SIMPLE_GREEDY] =3D &objagg_opt_simple_greedy, +}; + +static int objagg_hints_obj_cmp(struct rhashtable_compare_arg *arg, + const void *obj) +{ + struct rhashtable *ht =3D arg->ht; + struct objagg_hints *objagg_hints =3D + container_of(ht, struct objagg_hints, node_ht); + const struct objagg_ops *ops =3D objagg_hints->ops; + const char *ptr =3D obj; + + ptr +=3D ht->p.key_offset; + return ops->hints_obj_cmp ? ops->hints_obj_cmp(ptr, arg->key) : + memcmp(ptr, arg->key, ht->p.key_len); +} + +/** + * objagg_hints_get - obtains hints instance + * @objagg: objagg instance + * @opt_algo_type: type of hints finding algorithm + * + * Note: all locking must be provided by the caller. + * + * According to the algo type, the existing objects of objagg instance + * are going to be went-through to assemble an optimal tree. We call this + * tree hints. These hints can be later on used for creation of + * a new objagg instance. There, the future object creations are going + * to be consulted with these hints in order to find out, where exactly + * the new object should be put as a root or delta. + * + * Returns a pointer to hints instance in case of success, + * otherwise it returns pointer error using ERR_PTR macro. + */ +struct objagg_hints *objagg_hints_get(struct objagg *objagg, + enum objagg_opt_algo_type opt_algo_type) +{ + const struct objagg_opt_algo *algo =3D objagg_opt_algos[opt_algo_type]; + struct objagg_hints *objagg_hints; + int err; + + objagg_hints =3D kzalloc(sizeof(*objagg_hints), GFP_KERNEL); + if (!objagg_hints) + return ERR_PTR(-ENOMEM); + + objagg_hints->ops =3D objagg->ops; + objagg_hints->refcount =3D 1; + + INIT_LIST_HEAD(&objagg_hints->node_list); + + objagg_hints->ht_params.key_len =3D objagg->ops->obj_size; + objagg_hints->ht_params.key_offset =3D + offsetof(struct objagg_hints_node, obj); + objagg_hints->ht_params.head_offset =3D + offsetof(struct objagg_hints_node, ht_node); + objagg_hints->ht_params.obj_cmpfn =3D objagg_hints_obj_cmp; + + err =3D rhashtable_init(&objagg_hints->node_ht, &objagg_hints->ht_params)= ; + if (err) + goto err_rhashtable_init; + + err =3D algo->fillup_hints(objagg_hints, objagg); + if (err) + goto err_fillup_hints; + + if (WARN_ON(objagg_hints->node_count !=3D objagg->obj_count)) + goto err_node_count_check; + + return objagg_hints; + +err_node_count_check: +err_fillup_hints: + objagg_hints_flush(objagg_hints); + rhashtable_destroy(&objagg_hints->node_ht); +err_rhashtable_init: + kfree(objagg_hints); + return ERR_PTR(err); +} +EXPORT_SYMBOL(objagg_hints_get); + +/** + * objagg_hints_put - puts hints instance + * @objagg_hints: objagg hints instance + * + * Note: all locking must be provided by the caller. + */ +void objagg_hints_put(struct objagg_hints *objagg_hints) +{ + if (--objagg_hints->refcount) + return; + objagg_hints_flush(objagg_hints); + rhashtable_destroy(&objagg_hints->node_ht); + kfree(objagg_hints); +} +EXPORT_SYMBOL(objagg_hints_put); + +/** + * objagg_hints_stats_get - obtains stats of the hints instance + * @objagg_hints: hints instance + * + * Note: all locking must be provided by the caller. + * + * The returned structure contains statistics of all objects + * currently in use, ordered by following rules: + * 1) Root objects are always on lower indexes than the rest. + * 2) Objects with higher delta user count are always on lower + * indexes. + * 3) In case multiple objects have the same delta user count, + * the objects are ordered by user count. + * + * Returns a pointer to stats instance in case of success, + * otherwise it returns pointer error using ERR_PTR macro. + */ +const struct objagg_stats * +objagg_hints_stats_get(struct objagg_hints *objagg_hints) +{ + struct objagg_stats *objagg_stats; + struct objagg_hints_node *hnode; + int i; + + objagg_stats =3D kzalloc(struct_size(objagg_stats, stats_info, + objagg_hints->node_count), + GFP_KERNEL); + if (!objagg_stats) + return ERR_PTR(-ENOMEM); + + i =3D 0; + list_for_each_entry(hnode, &objagg_hints->node_list, list) { + memcpy(&objagg_stats->stats_info[i], &hnode->stats_info, + sizeof(objagg_stats->stats_info[0])); + i++; + } + objagg_stats->stats_info_count =3D i; + + sort(objagg_stats->stats_info, objagg_stats->stats_info_count, + sizeof(struct objagg_obj_stats_info), + objagg_stats_info_sort_cmp_func, NULL); + + return objagg_stats; +} +EXPORT_SYMBOL(objagg_hints_stats_get); + MODULE_LICENSE("Dual BSD/GPL"); MODULE_AUTHOR("Jiri Pirko "); MODULE_DESCRIPTION("Object aggregation manager"); diff --git a/lib/test_objagg.c b/lib/test_objagg.c index ab57144bb0cd..3744573b6365 100644 --- a/lib/test_objagg.c +++ b/lib/test_objagg.c @@ -87,6 +87,15 @@ static void world_obj_put(struct world *world, struct ob= jagg *objagg, =20 #define MAX_KEY_ID_DIFF 5 =20 +static bool delta_check(void *priv, const void *parent_obj, const void *ob= j) +{ + const struct tokey *parent_key =3D parent_obj; + const struct tokey *key =3D obj; + int diff =3D key->id - parent_key->id; + + return diff >=3D 0 && diff <=3D MAX_KEY_ID_DIFF; +} + static void *delta_create(void *priv, void *parent_obj, void *obj) { struct tokey *parent_key =3D parent_obj; @@ -95,7 +104,7 @@ static void *delta_create(void *priv, void *parent_obj, = void *obj) int diff =3D key->id - parent_key->id; struct delta *delta; =20 - if (diff < 0 || diff > MAX_KEY_ID_DIFF) + if (!delta_check(priv, parent_obj, obj)) return ERR_PTR(-EINVAL); =20 delta =3D kzalloc(sizeof(*delta), GFP_KERNEL); @@ -115,7 +124,7 @@ static void delta_destroy(void *priv, void *delta_priv) kfree(delta); } =20 -static void *root_create(void *priv, void *obj) +static void *root_create(void *priv, void *obj, unsigned int id) { struct world *world =3D priv; struct tokey *key =3D obj; @@ -268,6 +277,12 @@ static int check_stats_nodelta(struct objagg *objagg) return err; } =20 +static bool delta_check_dummy(void *priv, const void *parent_obj, + const void *obj) +{ + return false; +} + static void *delta_create_dummy(void *priv, void *parent_obj, void *obj) { return ERR_PTR(-EOPNOTSUPP); @@ -279,6 +294,7 @@ static void delta_destroy_dummy(void *priv, void *delta= _priv) =20 static const struct objagg_ops nodelta_ops =3D { .obj_size =3D sizeof(struct tokey), + .delta_check =3D delta_check_dummy, .delta_create =3D delta_create_dummy, .delta_destroy =3D delta_destroy_dummy, .root_create =3D root_create, @@ -292,7 +308,7 @@ static int test_nodelta(void) int i; int err; =20 - objagg =3D objagg_create(&nodelta_ops, &world); + objagg =3D objagg_create(&nodelta_ops, NULL, &world); if (IS_ERR(objagg)) return PTR_ERR(objagg); =20 @@ -357,6 +373,7 @@ static int test_nodelta(void) =20 static const struct objagg_ops delta_ops =3D { .obj_size =3D sizeof(struct tokey), + .delta_check =3D delta_check, .delta_create =3D delta_create, .delta_destroy =3D delta_destroy, .root_create =3D root_create, @@ -793,7 +810,7 @@ static int test_delta(void) int i; int err; =20 - objagg =3D objagg_create(&delta_ops, &world); + objagg =3D objagg_create(&delta_ops, NULL, &world); if (IS_ERR(objagg)) return PTR_ERR(objagg); =20 @@ -815,6 +832,170 @@ static int test_delta(void) return err; } =20 +struct hints_case { + const unsigned int *key_ids; + size_t key_ids_count; + struct expect_stats expect_stats; + struct expect_stats expect_stats_hints; +}; + +static const unsigned int hints_case_key_ids[] =3D { + 1, 7, 3, 5, 3, 1, 30, 8, 8, 5, 6, 8, +}; + +static const struct hints_case hints_case =3D { + .key_ids =3D hints_case_key_ids, + .key_ids_count =3D ARRAY_SIZE(hints_case_key_ids), + .expect_stats =3D + EXPECT_STATS(7, ROOT(1, 2, 7), ROOT(7, 1, 4), ROOT(30, 1, 1), + DELTA(8, 3), DELTA(3, 2), + DELTA(5, 2), DELTA(6, 1)), + .expect_stats_hints =3D + EXPECT_STATS(7, ROOT(3, 2, 9), ROOT(1, 2, 2), ROOT(30, 1, 1), + DELTA(8, 3), DELTA(5, 2), + DELTA(6, 1), DELTA(7, 1)), +}; + +static void __pr_debug_stats(const struct objagg_stats *stats) +{ + int i; + + for (i =3D 0; i < stats->stats_info_count; i++) + pr_debug("Stat index %d key %u: u %d, d %d, %s\n", i, + obj_to_key_id(stats->stats_info[i].objagg_obj), + stats->stats_info[i].stats.user_count, + stats->stats_info[i].stats.delta_user_count, + stats->stats_info[i].is_root ? "root" : "noroot"); +} + +static void pr_debug_stats(struct objagg *objagg) +{ + const struct objagg_stats *stats; + + stats =3D objagg_stats_get(objagg); + if (IS_ERR(stats)) + return; + __pr_debug_stats(stats); + objagg_stats_put(stats); +} + +static void pr_debug_hints_stats(struct objagg_hints *objagg_hints) +{ + const struct objagg_stats *stats; + + stats =3D objagg_hints_stats_get(objagg_hints); + if (IS_ERR(stats)) + return; + __pr_debug_stats(stats); + objagg_stats_put(stats); +} + +static int check_expect_hints_stats(struct objagg_hints *objagg_hints, + const struct expect_stats *expect_stats, + const char **errmsg) +{ + const struct objagg_stats *stats; + int err; + + stats =3D objagg_hints_stats_get(objagg_hints); + if (IS_ERR(stats)) + return PTR_ERR(stats); + err =3D __check_expect_stats(stats, expect_stats, errmsg); + objagg_stats_put(stats); + return err; +} + +static int test_hints_case(const struct hints_case *hints_case) +{ + struct objagg_obj *objagg_obj; + struct objagg_hints *hints; + struct world world2 =3D {}; + struct world world =3D {}; + struct objagg *objagg2; + struct objagg *objagg; + const char *errmsg; + int i; + int err; + + objagg =3D objagg_create(&delta_ops, NULL, &world); + if (IS_ERR(objagg)) + return PTR_ERR(objagg); + + for (i =3D 0; i < hints_case->key_ids_count; i++) { + objagg_obj =3D world_obj_get(&world, objagg, + hints_case->key_ids[i]); + if (IS_ERR(objagg_obj)) { + err =3D PTR_ERR(objagg_obj); + goto err_world_obj_get; + } + } + + pr_debug_stats(objagg); + err =3D check_expect_stats(objagg, &hints_case->expect_stats, &errmsg); + if (err) { + pr_err("Stats: %s\n", errmsg); + goto err_check_expect_stats; + } + + hints =3D objagg_hints_get(objagg, OBJAGG_OPT_ALGO_SIMPLE_GREEDY); + if (IS_ERR(hints)) { + err =3D PTR_ERR(hints); + goto err_hints_get; + } + + pr_debug_hints_stats(hints); + err =3D check_expect_hints_stats(hints, &hints_case->expect_stats_hints, + &errmsg); + if (err) { + pr_err("Hints stats: %s\n", errmsg); + goto err_check_expect_hints_stats; + } + + objagg2 =3D objagg_create(&delta_ops, hints, &world2); + if (IS_ERR(objagg)) + return PTR_ERR(objagg); + + for (i =3D 0; i < hints_case->key_ids_count; i++) { + objagg_obj =3D world_obj_get(&world2, objagg2, + hints_case->key_ids[i]); + if (IS_ERR(objagg_obj)) { + err =3D PTR_ERR(objagg_obj); + goto err_world2_obj_get; + } + } + + pr_debug_stats(objagg2); + err =3D check_expect_stats(objagg2, &hints_case->expect_stats_hints, + &errmsg); + if (err) { + pr_err("Stats2: %s\n", errmsg); + goto err_check_expect_stats2; + } + + err =3D 0; + +err_check_expect_stats2: +err_world2_obj_get: + for (i--; i >=3D 0; i--) + world_obj_put(&world2, objagg, hints_case->key_ids[i]); + objagg_hints_put(hints); + objagg_destroy(objagg2); + i =3D hints_case->key_ids_count; +err_check_expect_hints_stats: +err_hints_get: +err_check_expect_stats: +err_world_obj_get: + for (i--; i >=3D 0; i--) + world_obj_put(&world, objagg, hints_case->key_ids[i]); + + objagg_destroy(objagg); + return err; +} +static int test_hints(void) +{ + return test_hints_case(&hints_case); +} + static int __init test_objagg_init(void) { int err; @@ -822,7 +1003,10 @@ static int __init test_objagg_init(void) err =3D test_nodelta(); if (err) return err; - return test_delta(); + err =3D test_delta(); + if (err) + return err; + return test_hints(); } =20 static void __exit test_objagg_exit(void) --=20 2.20.1