From patchwork Wed May 23 01:18:16 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kent Overstreet X-Patchwork-Id: 10421015 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id D33E860327 for ; Wed, 23 May 2018 12:06:17 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id C13D928DDC for ; Wed, 23 May 2018 12:06:17 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id B56BC28F2C; Wed, 23 May 2018 12:06:17 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED, T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from ucol19pa09.eemsg.mail.mil (ucol19pa09.eemsg.mail.mil [214.24.24.82]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 77C9828DDC for ; Wed, 23 May 2018 12:06:16 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.49,432,1520899200"; d="scan'208";a="702742218" Received: from emsm-gh1-uea11.ncsc.mil ([214.29.60.3]) by ucol19pa09.eemsg.mail.mil with ESMTP; 23 May 2018 12:06:15 +0000 X-IronPort-AV: E=Sophos;i="5.49,432,1520899200"; d="scan'208";a="13655937" IronPort-PHdr: =?us-ascii?q?9a23=3AU7Ig5x9BNzm56f9uRHKM819IXTAuvvDOBiVQ1K?= =?us-ascii?q?B61OMfIJqq85mqBkHD//Il1AaPAd2Araocw8Pt8InYEVQa5piAtH1QOLdtbD?= =?us-ascii?q?Qizfssogo7HcSeAlf6JvO5JwYzHcBFSUM3tyrjaRsdF8nxfUDdrWOv5jAOBB?= =?us-ascii?q?r/KRB1JuPoEYLOksi7ze+/94HdbglSmDaxfa55IQmrownWqsQYm5ZpJLwryh?= =?us-ascii?q?vOrHtIeuBWyn1tKFmOgRvy5dq+8YB6/ShItP0v68BPUaPhf6QlVrNYFygpM3?= =?us-ascii?q?o05MLwqxbOSxaE62YGXWUXlhpIBBXF7A3/U5zsvCb2qvZx1S+HNsL4V7A0XS?= =?us-ascii?q?mp4bltRhHmlSwLMyc1/HzLhsB1iq9QvRCvqAFlw4PMYI+bKvRwcKDac90HXW?= =?us-ascii?q?pMXNtdWiJODYygYIUAEfEBMP1Er4T/vVYCsQGzCRWyCO7p1zRGhmX23ao/0+?= =?us-ascii?q?k5FA/JwgogH84Tu3rNstX6Kr0SUfupzKnS0zrMce9W0ir65YjLbB8hp+2MUa?= =?us-ascii?q?h3ccrP10YvDRjFjkmKqYP7ITyVyv8As2ee7+V6VOKvj3QrpB12ojiq38ohjJ?= =?us-ascii?q?TCiIENyl3c6Cl0z4k4Kce4RUJme9KoDpRduz+AO4drWs8vQXxktDwkxrAItp?= =?us-ascii?q?O3ZjUGxZY5yxLFdfCLboeF7xT+X+iLOzh4nmhqeLeniha39kiv1/PzW9Gv0F?= =?us-ascii?q?ZPsipFit7Mtm0R1xDL6siIVP99/kC51DaTzQ/T8OBEIV0vlabBN54gwqI/lp?= =?us-ascii?q?oUsUjZGC/5hF72g7OMekUh++io7/zrYrTgppCCK495khzyP6shl8ClAek0Lx?= =?us-ascii?q?ICU3aU9OiizrHv4FX1QLBQgf03lqnZvoraJcMepqOhGA9azIIj6xe5Dze739?= =?us-ascii?q?UUhGIILFVYeBKBk4fmJUrOLevkDfa/n1uskDBry+rAPr36GJrBNHfDkLD/fb?= =?us-ascii?q?pl8U5T1BIzzcxD55JTErwBIvXzWknru9zEDh82KQq0zv3lCNV60IMeXHiAAr?= =?us-ascii?q?SFMKzMq1+I/fgjI+6WZI8aoDz9MeQq5+byjX8lnl8QZaup3ZkNZ3+kHfRmOE?= =?us-ascii?q?KZYXztgtcfCmoKsA4+TPHliVKZTD5TYWqyX78m6jE8EoKmAp/JRpqxj7yZwC?= =?us-ascii?q?e7AppWa3heCl+SCnjnaYOEW/YQaCKVOcJhkyILWqa/RIM70hGurgD6waJ9Lu?= =?us-ascii?q?XI4i0YqY7j1N9t6uLOkhEy8zp0ANmD3GGJTmF5hXkHSCEs3KB4u0B9zU2D0a?= =?us-ascii?q?dgifxCCdNT/+9JUhs9NZPE0uN6F8r9Whjac9iVT1amR8mpDisqTtIt2dMOZV?= =?us-ascii?q?hyG8m6hBDZwyWqG6MVl6CMBJEs7K3cx2L+J9x8y3bdz6Qhl0MpQtFONW29nq?= =?us-ascii?q?5/8xLcCJLXnEmDkKaqb6sc1jbX9Gif1WqOoF1YUAloXKXEW3AfelXZrdDn6U?= =?us-ascii?q?PHUbCuFa4nMwtaxM6FMqtFdNvpjVBcS/fiPNTReGWxmmiqCRaP3LOMY5Lge3?= =?us-ascii?q?8B0yXFFEgEjwcT8G6INAg/AiehpnzRDCZ1GFLhfUzj7O5+qGmhQU8s1QGKaE?= =?us-ascii?q?9h2KSp9R4Jn/CcTOkT3r0csic7tzp0BEq9387RC9eYqQphZr9TYdUh71dGzm?= =?us-ascii?q?LUrAl9PoShL6x7nV4ffR93s1np1xVtBYVKidIqo28yzApuNaKY10tMdzCC0p?= =?us-ascii?q?DzPb3XN3L//BO1ZK7V3VHezcya+qAV6PQ3s1/jph2mFlI+83V71NlYy2GT6Y?= =?us-ascii?q?jQDAoTT53xSF06+AJmqLHfeCU94JnU1XJ0O6murjDCw84pBPciyhu4Y9hQKq?= =?us-ascii?q?eEGxHpE80GB8muL/cnm0O1YRIFIu9S8rI0P8K8ePec3q6kIvpgliq8jWtb+I?= =?us-ascii?q?B9zl6M9y1kR+7SwpkK3uqV3gSCVzbzlluhtN74mZxcbzEIAmW/0TTkBJJWZq?= =?us-ascii?q?BqZoYLB32uI8qsxtVinJPtQHhY9FmtBlMDwsCpfwCeb1rj0g1MzU4Xu2ComT?= =?us-ascii?q?OkzzxolDEktqSe0zbKw+T+ahUHIHVLSXJ8jVjyO4i7lM0aXE2yYwgujhul6l?= =?us-ascii?q?7wx7JHq6RnM2nTXUBIcjDoL2FjTqSwqr2CY9RV5Jw0sSVXV+K8YV+BR775oh?= =?us-ascii?q?sa1TnsH3FZxDwhcDGqoJr5lQRgiG2BNHZzsGbZecZoyBfb5dzcXuJR0iMdRC?= =?us-ascii?q?ZmjTnXB168P8Sm/NiPjJfDquG+V2SgVpJPainn14WAuzWn5WdyGx2wg+izms?= =?us-ascii?q?H7EQg9ySL7zd5qVSHMrBnieInky6O6MOx8c0lzGV/z99F6Fpt5kosqi5EawW?= =?us-ascii?q?IaiYmN/XobjWfzNs1W2aHgY3oLXj4G2N3V7xbj2E14KHKG2Z75Wm+awst7aN?= =?us-ascii?q?mwenkW1T4l78BWFKeU66RJnTNvrVqlqQLef+B9kS0byfsy9nEamfoEuBc2zi?= =?us-ascii?q?qDGLASBlNUPTfrlxSV9dCxsLtYZGiocbiq20pxg8qtDLecrQFAQHz5YIstHT?= =?us-ascii?q?ds7sVjN1LByGPz6of5d9TLc9ITsACbkxfag+hTNp0xiuIAhTB7NmLloX0l1+?= =?us-ascii?q?k7gAR23Z6goYiHL35g8764Ah5ENjz5fs0T9SvrjapEmcaWxY+vFI17GjoXRJ?= =?us-ascii?q?voUe6oEDUKuPTkNweOFCMzp2yeGbrYEw+f5llpr27TE5CrMHGXIWcWwc9kRB?= =?us-ascii?q?aDOExVmBoUUykinp4lCgCqw9TscElj6TAX+l74rR5Mx/lmNxbhT2jfox2oZS?= =?us-ascii?q?0sSJiFKxpW7B9N6FvJMcCE6eJzBS5Y9IW7rAORMmybexhIDWYRV0OZG1/jO7?= =?us-ascii?q?6u5d/c8+SFHee+MeXBYa+Pqe1fUPeIw4ij0o148DaQLs+PJGVtD+Un2kpfWn?= =?us-ascii?q?B0A8rZmy8RRCMKjCLCdcibpAu7+i1stc2w6ujkWAf16YuIEbtSPs1l+wqqjq?= =?us-ascii?q?ebK+6QmCF5JC5e1pMW33DI0KAf0UUciyFvbTmtCqgAtSDMTKLWgKBXCQIUay?= =?us-ascii?q?JpO8tM9a482RNNOcHDgNPvyrF4luI1C0tCVVH5gc6mfssGI2W8NFPcGEaLL6?= =?us-ascii?q?6KJSbVzM7re6+8UqNfjOFVtx22pDaaHFTuMSiDljnzShCvKvtAjS+BMxxCo4?= =?us-ascii?q?G9dRBtBXLkTNL8ZR2xKMV3giEuwb0omnPKMnYRMT59c0NJqr2f8zhYj+5lFG?= =?us-ascii?q?Nf9HplKvOImyGD7+nXMpwWq+dkAjxol+JG53Q306Ba7CBLRPxynivftcNhrE?= =?us-ascii?q?+9nemO0DVnVgBCqjFRhIKEpU9iI7nW9oFcWXbY+xIA9X+fCxsQqNt7FNLioK?= =?us-ascii?q?dQysDRm6L1LTdN6dPU/c8HCMjTJ8OLKn0hMQDmGDTMFgsKUSarNX3Dh0xaiP?= =?us-ascii?q?yS6nqVrp0gppj2n5oPS6FUVFouGfMADURqAt8CLYxrUTMjlL6UkNQH5WGirB?= =?us-ascii?q?XLQsVVoIzHXOqIAfrzMDaZkaVEZxwQzLP6LYQSNpX720tmall7gITFBVHdXd?= =?us-ascii?q?VMoi19dA87vl9B8H9kTm08w0jlcB+i4GcPFf6omR47kg1+bvo3+zfo+Fo3JV?= =?us-ascii?q?3KpDAskEYrn9XlmjORcD/rIKe2Q45WFzL+t1ItPZPjXwZ1cQqykFR+NDjaXL?= =?us-ascii?q?JekaFvdXp3hw/copZAAv9cTbdZbx8Xy/GXf+8o3kpcqym9w09I+/fFA4N4lA?= =?us-ascii?q?Q2aZ6ss25A2wV7YdEoP6PQOqtJwUVLhq+VpCCozPoxwAgQJkYW7mydZDMIuF?= =?us-ascii?q?YJNrk6Jyuk5Ops5hKemzFbYmgDS+Iqou529kM6I+mAyyXg06RdJUC3Nu2fKL?= =?us-ascii?q?iUu2fGlc6VWF8w0VkIl0Zd97hszcgja1aUV1wozLaJDBQGK87CKQBTb8pP+3?= =?us-ascii?q?neZjqBseLIwZ1pJYq9DfzoQfWItKkKnkKuBBwpEJgU7sQdApms11nVLdvmLL?= =?us-ascii?q?4AzhUt+ATrJVWeAftUeRKKkC0IrNqlwJ9xw4ZdOikXAX9hPiWv+rbXuggqje?= =?us-ascii?q?KZU9cyY3cVQpULOWozWMy6nS5ZuHJAAyOs3+0CyQiN9Tn8qj3eDDnhddZjYu?= =?us-ascii?q?mbZQ90AtGs5To/67S2iULQ8pjGPG71K9Jit8TV5uwHuZaIFelUTaJnvEfGm4?= =?us-ascii?q?hUXXuqU3TAEdStPZj/d5EsbcDoCna9SlG/kTQ1T8btM9atKaiIhRroS55Nvo?= =?us-ascii?q?eGxj4uKcizGyoCFBd3ouEM+LhzZRYfY5YhZx7nqRg+PbSlIAiEytWuX3qtKT?= =?us-ascii?q?xOQvZDz+W1faBYwjEwYe+9zHsgSpA6wPet8U4RWp4FkhHeyeykZ4lEXij5Am?= =?us-ascii?q?ZddBnXpSoli2hhMf4/wv0lzxPStlkTKCuGdPBzaGNeodEzG1eSIXRwCmo3Q1?= =?us-ascii?q?+cjIXD4g6w37Ac5SRdhdNU3fdDsHfgop/VeCisV7CzqZXJryogasAroqNrPY?= =?us-ascii?q?P/IsuGtZbenj3FQ5nTqQCFUTC1GOREldRKJyJYWvZIk3k/OcMaoYpB9VYxVs?= =?us-ascii?q?AmKrxKEqYsvLOqZiR4DS4Tyy8ZWJiN3TIYjee6x7TakhCQcIk/PxwfqplChM?= =?us-ascii?q?USUzJuaCMEuKCjT5nWl3ODSmUTOAcT6gBM6xgalo5+eeDl5ITIQYRJyz5RpP?= =?us-ascii?q?J0STXEGYVy91v8UWGWmln4SPOuk+Cz2gJS1v3s2MEBWBFjEUhd2/pWlkwwJb?= =?us-ascii?q?5tMakQo4jKviWLdU7hvWLtyeqmJEVKxsHOcV33EpbFv3LmUiIA4X0UWZNPyH?= =?us-ascii?q?bHGJQOlAp5bb0mpElQLICjYUny/TokyJp1H7OgT8Ck204lrWoaRyetC9dBC/?= =?us-ascii?q?tpsEjNVz1hfp+ms4jqNItKQm9I5pKdr0lWkF93Py6+05pcJNlH4iQQUzhXvT?= =?us-ascii?q?WdoNyyRdVB2c9xEZABOcpwtGnmGKxaIpiRv2M5taH1xn/f5T88rE+wxC+vFK?= =?us-ascii?q?+gU+JZ42oeFx01J2uDt0YvDvEj8mPJ/1/RtVB0+vtUCaKUjUVtujp9GI5BBi?= =?us-ascii?q?pR33C/M1tzVGVGs/ldKKnNaMNcTeU9aQOtNhAjG/MrxFCG/UZxnXjleSNyrR?= =?us-ascii?q?da9zrbXwYqSSkfmq3tliEGqsG7JT8aTIpFbS8/YCjYKwKUgzxXsQ1ba0FtRZ?= =?us-ascii?q?AWHMhJ9K0c3YRJ4MXOU0CsJj8ZXBZ6LAI3zeJflVJfsEWfYS3dFRGoderVvR?= =?us-ascii?q?JqYcect9WpLPPk/AddlozoruY497kZR3K8nQ2hW9fer5XztteSrEuBaL/4M/?= =?us-ascii?q?GgYX/GVDXMkQqwiqk6AJbX5CXTLQ5bK4VgyXU+f5jhCGnLPRBYKKIHPUZbUr?= =?us-ascii?q?p6adpeqOBAe8BkYLoJ+bNqBh+fQxPgAoivrP1YIVbPWTTRNT+O//e5oY3N8b?= =?us-ascii?q?zdUvTvadaUx3nZWa53OIl16SXjEbfwzYBe4lb22utq9k5iS1jJKTqBrNP6Jg?= =?us-ascii?q?MP/saiaFDvvpg0HTPSHJdwkWbixkBaeMoRWC2m6pMYyIlW6HzoU+J3zlDzsP?= =?us-ascii?q?FO97lj8YQ34apmycG6JafILvRVrFFoDwOIBgpw8JUtG29/S3pXYuAPNPfbZb?= =?us-ascii?q?4Zgtz2q+DrC6wX7wWY++NEadvGI0HBntewCjSHRBNZgggOsj8aIRGa1/KfnK?= =?us-ascii?q?90U8mlr/Dj2k0x+1i+MgIGzLd16IeG+6qIofTabx7PwrkERKfqXMLzrrIju0?= =?us-ascii?q?+I4/0riqIOcHRvYwK7COgdStIdxmD4wKAsySIhCMLDH7Tl+PJZVnI5mDzgm4?= =?us-ascii?q?pnEFUNBvMUB6eL8phCnmclgezWKMcacqdYmmaADRSkCKMNyWa36yuLJ2lomh?= =?us-ascii?q?TO0xb2QWOv41/5szR1QS7Nz9j5lEpaSKW3BElVXyqzOk94qymDPAz2u9rroa?= =?us-ascii?q?419l05MnT4tNKRk2usILdXH9b6JNGcOiQ0qkwYg4A2Rty1w48bAcC9INAT8H?= =?us-ascii?q?5gcvTe93mnkyhbo6dIn4De+N2a+u3LHXm8iK2Xs7SNxTFCxXcioV4y8cugOe?= =?us-ascii?q?/S59KUX/ukzWERTz1wuwHZRR66tqTbr0wIOUyMyErEg40KPspX3HYi1EHm5f?= =?us-ascii?q?QjQMop+wVDEobNfO8NpTfuNzTq21mffsg3Vi6E0zRNBF71FkN4GKck0mLqoM?= =?us-ascii?q?3JjWvQ+0EvRoRob0zonwB3AJk4KUMj71gX2CkDHREWaR+FCLGoBELlLZYLVE?= =?us-ascii?q?UYcRSIxqS6dbs33Ux9xbOv/uzTYfZ/B6UTLPZdiBCBnFxBFpIRq60eT6p2e0?= =?us-ascii?q?VB+67PugjiF4/nUuDplXUqL/26XNxa8cACunsm4wa/WwSv6ZdZ4LYGk5CEbK?= =?us-ascii?q?hEbobQvMpk9Udo+SYPdjBRgBh4lx65Xv4TpOb/4tjct5qk7f2uW7gpR+UW8R?= =?us-ascii?q?g0Gmt/goD0gF89u9HW1/1TRpfTiYvh7ABHO2SKt5rC0xlgNeoOLJqmfLBh93?= =?us-ascii?q?obICgeI2gBPcGMZ/k95C9tNy7T50dZD8MJat4ZM9DBmQdOik3mQLtT7NbUGk?= =?us-ascii?q?eEC4dvcMAl92X3xywu8ZsnS+ru9TC4K5be71FLIvNCgz5hlN3HpOcPx/rdFj?= =?us-ascii?q?Ib4X6Daxh62imC0YWCC+7s/eWQz9HZT1EGHik2U4dbPjaN5QynRu6olJr0Uw?= =?us-ascii?q?KU68nzgIk9dEKRXXGxgqUFsrhWHu5Elyr73yJSFobriPKJq9Cs8ndYtkVbEI?= =?us-ascii?q?Zv6h3IAKRfPothNhT+jcSrQlV8CTb+eMHTbRoiou2Wxv0D4+9mLUvxeZcbIg?= =?us-ascii?q?4Yy7L98XdVTBVhSLD4vladRu8QasFpSPXaoXBJ845gLbEAPESFrpzwsjhIsE?= =?us-ascii?q?w2ABMuaLIooTxack7OnQNLVKbwvL4NkRAcUdl/uU9NBW28ImQ+6CTbVa5Nlq?= =?us-ascii?q?meFOQV8imPTqwJS0hoNyJ+QxC22JVpYLapn+pIsmBBniN7vvcq1SZqRB2iti?= =?us-ascii?q?3wv6gNwy4v+KmktDUdvnxIVv6RnDnOCVVf1/kKlqMcC3H+6VygfnkMcpb97K?= =?us-ascii?q?NgJcT6+okr+24/bgk7fy0aQeSgDDn9j62WDYyLsdJcnACCtd7PbL+yKCgSM6?= =?us-ascii?q?oyyQjnR3djyATemwxo8GQTSDW68NAkPJm9OdoixiewF2nbbEwM4qJVv8Tvrl?= =?us-ascii?q?MLSeo2aU97wGp9yMSHQTcNRMPXEWYvkgckcXlEcI5E6RICEKkohiiHs7Je/g?= =?us-ascii?q?EQejjUCZil+ojMksfUw3kyU8llynjQpqKbmpMgyGdllM9s7i6SpHQScPTVU8?= =?us-ascii?q?ttAnj1y4dexvXyZ/GssuAcVItm06+sUP4YPcml/mu6wpJqWlWqxr4GBVq2LP?= =?us-ascii?q?cDxqvHUyeiUWCYXP6EfHSMnzY4NE7y4gKlLkM2aMdMsUA9NurChphBlwzuS7?= =?us-ascii?q?90QT+QpVDDxmw5Lewabx42uJugewESTu4efeucJe81z/AlFVsMaWPJHStxC+?= =?us-ascii?q?+rvl6tnJR7N29m4UrkfeTn6hrmP8eKGhkYDY7aqYZ8+f6/RmKGI39g1hxyPF?= =?us-ascii?q?Jv+ufZDVsxs/FTc5eLkdjXndR73vYPd+1xPi0lpt4ThoVj5JGP0MeEdBHe0p?= =?us-ascii?q?f/KNLOr/iGHfLf1UUqe2BdUrofew/14Zs1PsJqE4HUSL9YuwkMQKs3WposM0?= =?us-ascii?q?/v+6xuagB+aAjcYPKzmMau7vyKfJx8tXLQ70x2KCbapg1Fzea7CxF4K9ijhG?= =?us-ascii?q?33CJQxQC9R6tNqFx1qFZdOHMVGqBCoR9aLmaW/mvew/U1gsuMHuKa2DerFkJ?= =?us-ascii?q?y2xYh+XJhy4U2NISbfA7Rtjk15j+O0xPDa3d25DcLkZMNBT+VwX3TEdq6DG4?= =?us-ascii?q?KzNzaDEtzzdlQA8LOG1r99FBKLa2SxRKeCtSu5JN148E47zcp+Z+OVwzszq/?= =?us-ascii?q?nX1cXaYHlWoDm4sn+VP5sZ60bFQaTFXxZVYfmI6mBoGesQd4SwvOMPN8Eyhc?= =?us-ascii?q?KV4gVb8jtPyo2GLrKno0uK3Vh0JrzBK068+Cs/RcEtPhmlKlc2jGLF4iDeDH?= =?us-ascii?q?JAaM+6JNN2nMyYAwDF6Ex4mGVrbWlETDm7DeyNMHQWjprtLDaB8xhGWpNax7?= =?us-ascii?q?TtK0clqq2/T/VpMZxZmOKs8a8KisttNzqQFZpnBw37d5ROF2IBSOjCoUMnJB?= =?us-ascii?q?sNsrxzX4YxNv3saE8EMULV0Srp1kOCykz7cdWwybyEaDgb6HRJzr/JkHBMqg?= =?us-ascii?q?C1tOzfg5jLX7XQbZWwV/nXPQ=3D=3D?= X-IPAS-Result: =?us-ascii?q?A2DKBABhWAVb/wHyM5BcHQEBBQELAYNBA4EEWyiLe1+MB?= =?us-ascii?q?IJuGpM3FIFWGRgTAYRAgichNBgBAgEBAQEBAQIBaxwMQhABgWIkglcCJBMGA?= =?us-ascii?q?Q0OEgsBAgECCQIFECsICAMBHQIOAwEFAQsYBwsFGASDAYFoAQMVA55pPIxuF?= =?us-ascii?q?gUBF4JwBX8EAYJIChkmDVVXgXQCBhKHKHyBVD+BD4JYgwSBbQQBDAYBNIU/A?= =?us-ascii?q?pguLAcCgWeJc4J0C4dWhSuKL4YpAgQCBAUCBQ8hgQQcOGFxcFAxghKCFAkDF?= =?us-ascii?q?4NFihxSU3kBAQEohFGFHwEOF4IgAQE?= Received: from tarius.tycho.ncsc.mil ([144.51.242.1]) by emsm-gh1-uea11.NCSC.MIL with ESMTP; 23 May 2018 12:06:13 +0000 Received: from prometheus.infosec.tycho.ncsc.mil (prometheus [192.168.25.40]) by tarius.tycho.ncsc.mil (8.14.4/8.14.4) with ESMTP id w4NC6DdM020954; Wed, 23 May 2018 08:06:13 -0400 Received: from tarius.tycho.ncsc.mil (tarius.infosec.tycho.ncsc.mil [144.51.242.1]) by prometheus.infosec.tycho.ncsc.mil (8.15.2/8.15.2) with ESMTP id w4N1IhG4036651 for ; Tue, 22 May 2018 21:18:43 -0400 Received: from goalie.tycho.ncsc.mil (goalie [144.51.242.250]) by tarius.tycho.ncsc.mil (8.14.4/8.14.4) with ESMTP id w4N1IlLw026098 for ; Tue, 22 May 2018 21:18:47 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A1BYAgABwQRbly0bGNZcHgEGDINAgWIoj?= =?us-ascii?q?FmMFoJuGpM2gXgLLIRAgiMhNRcBAgEBAQEBAQIUAQEBAQEGGAZLhWIZARsdAQM?= =?us-ascii?q?SEFwCEQEFASMSgyKBaAEDFQOeYDyMbhYFAReCcAV/BAGCSAoZJg1UV4F0AgYSh?= =?us-ascii?q?yd8gVQ/gQ+CWIMEgW0RhXoCmCMsBwKBZ4lxgnQLh1OFK4oqhikCBAIEBQIFDyG?= =?us-ascii?q?BBB0BgghwgQGCEoIUCQMOCYNFihxSU3krilQBJYIgAQE?= X-IPAS-Result: =?us-ascii?q?A1BYAgABwQRbly0bGNZcHgEGDINAgWIojFmMFoJuGpM2gXg?= =?us-ascii?q?LLIRAgiMhNRcBAgEBAQEBAQIUAQEBAQEGGAZLhWIZARsdAQMSEFwCEQEFASMSg?= =?us-ascii?q?yKBaAEDFQOeYDyMbhYFAReCcAV/BAGCSAoZJg1UV4F0AgYShyd8gVQ/gQ+CWIM?= =?us-ascii?q?EgW0RhXoCmCMsBwKBZ4lxgnQLh1OFK4oqhikCBAIEBQIFDyGBBB0BgghwgQGCE?= =?us-ascii?q?oIUCQMOCYNFihxSU3krilQBJYIgAQE?= X-IronPort-AV: E=Sophos;i="5.49,431,1520913600"; d="scan'208";a="283112" Received: from emsm-gh1-uea11.ncsc.mil ([214.29.60.35]) by goalie.tycho.ncsc.mil with ESMTP; 22 May 2018 21:18:46 -0400 IronPort-PHdr: =?us-ascii?q?9a23=3AIceA3hHd6zsSctVz8lqSSZ1GYnF86YWxBRYc79?= =?us-ascii?q?8ds5kLTJ7yr8uwAkXT6L1XgUPTWs2DsrQY07GQ6/iocFdDyK7JiGoFfp1IWk?= =?us-ascii?q?1NouQttCtkPvS4D1bmJuXhdS0wEZcKflZk+3amLRodQ56mNBXdrXKo8DEdBA?= =?us-ascii?q?j0OxZrKeTpAI7SiNm82/yv95HJbAhEmDSwbaluIBmqsA7cqtQYjYx+J6gr1x?= =?us-ascii?q?DHuGFIe+NYxWNpIVKcgRPx7dqu8ZBg7ipdpesv+9ZPXqvmcas4S6dYDCk9PG?= =?us-ascii?q?Au+MLrrxjDQhCR6XYaT24bjwBHAwnB7BH9Q5fxri73vfdz1SWGIcH7S60/VD?= =?us-ascii?q?K/5KlpVRDokj8KOSM5/m/JhMJ+j6VVrQm9qxBj2YPYfJuYOOZicq7bYNgURX?= =?us-ascii?q?BBXsFUVyFZB42zcY0PD/YcNuhBsYnyuUEOrQCiBQm2Guzg1CNIjWLx0K05ze?= =?us-ascii?q?shFx3G0BYnH9IQrnvUts71NLsIUe+r0qbI0S7Ob/xT2Tjn6YjIdgotru2LXb?= =?us-ascii?q?J1aMfcz1QkGQDdjliIt4DpIjyY2v4Tv2WU9eZsS+Cih3QopgxxujSixNoghp?= =?us-ascii?q?PXio8bxV3I7zh1zYQrKdGiVkJ3fNGpHZ1NvC+ALYR2WNktQ2RwtSY61LIGvZ?= =?us-ascii?q?m7cTAEx5o9yRDSdfKKfpaS7B//SOqcIC10i2x7d7K6nBay/lKsyujmWcm11F?= =?us-ascii?q?ZGtC9FktjItnwV1hzT7NaISudl80u/xDqC2Brf5v9LLEwui6bWKYQtz7Ewm5?= =?us-ascii?q?YLtETMBC72mEH4jK+McUUk//Cl6+f5bbXgup+QLYh0ih/gPaQ0gcy/Hf44PR?= =?us-ascii?q?YQUGiH4um827jj8lf4QLVOlPE5jq7ZsJXCKcQBuqG5GxNV0pok6xunFDepzt?= =?us-ascii?q?AYnXgBLFJYdxOKlJTpOlHSL/D4CvezmVKskCxxyPzcMb3hBYvNfTD/l+LlfL?= =?us-ascii?q?Bg+wtfxRA1wNR3+Z1ZEPcCLej1V0u3s8bXSlcnMhaz6/TqDtRjkIcfX3+fRK?= =?us-ascii?q?iDP+XPshvA7+E3JsGIZYkIqHPzLOUj6/fyjHg/31gHcu3hwpoTbGGQH/JoOU?= =?us-ascii?q?yVbHPgxNAbHiNCsRAzQ+/qoFmDVyNDaXGvWa41+jA8DsShF4iHDoSshqGRmT?= =?us-ascii?q?y2FYBMZ3xXT1WLHWrseq2aVPoWLiGfOMlslnoDT7flA5Qs0RCoqR/S16tsLu?= =?us-ascii?q?2S/DYR853kypw96+DNvRYq+DpqFNucz2qNCWZukSdAXD8y3Yh8rFZ7x1PF1r?= =?us-ascii?q?J3x7RcFNpO97ZTWwY2HYDTwvY8CN3oXA/FONCTRwWIWNKjVBI8SM555MEDeV?= =?us-ascii?q?1hAdivkliX3CesH/kSibGRH4Au/6/A93f0Lsd5jX3B0f9y3BEdXsJTODj+1e?= =?us-ascii?q?ZE/A/JCtuRyR/Lnru2dakawC/G/XuCymzLpkxDTQpsSvqaD00nSmCNhuzQvh?= =?us-ascii?q?OEQrKrErthNwJAzYiHK68ZItHqjFATXP74I5yeeGO+nW6sGAyFjq2Bdovkem?= =?us-ascii?q?gRnW3dBUEInhpV/COuOg03ByPnqGXbAQ=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BZAgABwQRbly0bGNZcHgEGDINAgWI?= =?us-ascii?q?ojFmMFoJuGpM2gXgLLIRAgiMhNRcBAgEBAQEBAQIBEwEBAQEBBhgGSwyCNSK?= =?us-ascii?q?CfxkBGx0BAxIQXAIRAQUBIxKDIoFoAQMVA55gPIxuFgUBF4JwBX8EAYJIChk?= =?us-ascii?q?mDVRXgXQCBhKHJ3yBVD+BD4JYgwSBbRGFegKYIywHAoFniXGCdAuHU4Uriiq?= =?us-ascii?q?GKQIEAgQFAgUPIYEEHQGCCHCBAYISghQJAw4Jg0WKHFJTeSuKVAElgiABAQ?= X-IPAS-Result: =?us-ascii?q?A0BZAgABwQRbly0bGNZcHgEGDINAgWIojFmMFoJuGpM2g?= =?us-ascii?q?XgLLIRAgiMhNRcBAgEBAQEBAQIBEwEBAQEBBhgGSwyCNSKCfxkBGx0BAxIQX?= =?us-ascii?q?AIRAQUBIxKDIoFoAQMVA55gPIxuFgUBF4JwBX8EAYJIChkmDVRXgXQCBhKHJ?= =?us-ascii?q?3yBVD+BD4JYgwSBbRGFegKYIywHAoFniXGCdAuHU4UriiqGKQIEAgQFAgUPI?= =?us-ascii?q?YEEHQGCCHCBAYISghQJAw4Jg0WKHFJTeSuKVAElgiABAQ?= X-IronPort-AV: E=Sophos;i="5.49,431,1520899200"; d="scan'208";a="13646270" X-IronPort-Outbreak-Status: No, level 0, Unknown - Unknown Received: from updc3cpa06.eemsg.mail.mil ([214.24.27.45]) by emsm-gh1-uea11.NCSC.MIL with ESMTP; 23 May 2018 01:18:44 +0000 X-EEMSG-check-005: 0 X-EEMSG-check-006: 000-001;92648355-27d3-47a8-a9e4-c5a0320953f2 Received: from localhost.localdomain (localhost [127.0.0.1]) by UPDCF3IC16.oob.disa.mil (Postfix) with SMTP id 40rF5c28Kyz2Vp8c for ; Wed, 23 May 2018 01:18:44 +0000 (UTC) Received: from UPDC3CPA08_EEMSG_MP24.eemsg.mil (unknown [192.168.18.19]) by UPDCF3IC16.oob.disa.mil (Postfix) with ESMTP id 40rF5b2Qngz2Vp8X for ; Wed, 23 May 2018 01:18:43 +0000 (UTC) Authentication-Results: UPDC3CPA08.eemsg.mail.mil; dkim=pass (signature verified) header.i=@gmail.com X-EEMSG-check-008: 19375761|UPDC3CPA08_EEMSG_MP24.csd.disa.mil X-EEMSG-SBRS: 2.7 X-EEMSG-ORIG-IP: 209.85.220.195 X-EEMSG-check-002: true X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0DlAADavgRbf8PcVdFcHgEGDIVKjFmMFoJuGpM2gXgLBSeEQIIjITQYAQIBAQEBAQECFAEBCQsLCCYlDIVWGQEbHQEDEhBcAhEBBQEjEoMigWgBAxWeZjyMbhYFAReCcAV/BAGCSAoZJg1UV4F0AgYJAQiHJ3yBVD+BD4JYgwSBbRGFegKYIywHAoFniXGCdAuHU4UriiqGKQIEAgQFAgUPIYEEHIIKcIEBghKCFAkDF4NFihxSU3krilQBJYIgAQE X-IPAS-Result: A0DlAADavgRbf8PcVdFcHgEGDIVKjFmMFoJuGpM2gXgLBSeEQIIjITQYAQIBAQEBAQECFAEBCQsLCCYlDIVWGQEbHQEDEhBcAhEBBQEjEoMigWgBAxWeZjyMbhYFAReCcAV/BAGCSAoZJg1UV4F0AgYJAQiHJ3yBVD+BD4JYgwSBbRGFegKYIywHAoFniXGCdAuHU4UriiqGKQIEAgQFAgUPIYEEHIIKcIEBghKCFAkDF4NFihxSU3krilQBJYIgAQE Received: from mail-qk0-f195.google.com ([209.85.220.195]) by UPDC3CPA08.eemsg.mail.mil with ESMTP; 23 May 2018 01:18:42 +0000 Received: by mail-qk0-f195.google.com with SMTP id a8-v6so16184694qkj.12 for ; Tue, 22 May 2018 18:18:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id; bh=22KFhFmdwV5OSzpdng7umygvztZQ//oTmtOmNF7zshQ=; b=qTzkK285GZM2rclcVdRdB+WzX1Tz0JwJqjOaHDJmA4hpdxABRUwwFr/0jYkIkkNOD2 Tj1upGNG4+1lgscsJfqph9X/pHAmgZ0HleUFHYEnEMCONmyw8Nu+bPuNOxJ+MoDeL17W jq1srLl4NlNMRFfOyeDltoww8NbKW2tmbfaeW9SvNLDDvy2SNa4VExXSLSeGOUeKuk2P RcNgruUkxqwFanEtYJ1aDcCVqwSFdkeGBg1QdKcnoLze/vdVc1ddT0i1k47y9jIpAzjB 5gfYI/BNLjChwgIm1V2zyZPqb4krt/eFozCS3h9a/9wTrDQ58TL0C5vUj+dERG69ew36 IwyQ== 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; bh=22KFhFmdwV5OSzpdng7umygvztZQ//oTmtOmNF7zshQ=; b=Sz0hOkGAx0AdBSz6UiL7724fNOCrLATGLYs96ORva6bjmkO4+cgM+NJ0bpn56K4Uhz feUvrK4mOv6CDILW62fjwVMBGof7I/W8NtLuryNLnOr9/6CeyfTtUpyptCyvACumHEo8 wTcDg+LZc9sdk2z1LL3aMvC/mgm9t5I0iAVFfFStylAPx8p6RTyw3t+QAdcSRO6/nZ8f WDHxwIHDOmoCLv+Jaf9siI9ZVLVPB1RxaAHKjh2dNydmVuROTuqgyTnSCvaOoSpLdMR1 /DhLmM3HavmX4efOkVSejn2IGPfCpUHHrywy22sQqUgXRID8JPzUWgbxkqEYePm+BMsY yiiA== X-Gm-Message-State: ALKqPwexLOzeDUcoTIx/VKaSANpqnpDaYLyLG+3KhnSr2o7qUGBZeyI6 70GZl24XzkpsWafqhSudeQ== X-Google-Smtp-Source: ADUXVKJcdmOdrD1N/ZgM+1lxC39BQyY7aMJu8dj+tAyVf57esgqTfHEfttuUVgabKkAy+/+dThex6g== X-Received: by 2002:a37:1860:: with SMTP id j93-v6mr688478qkh.11.1527038321484; Tue, 22 May 2018 18:18:41 -0700 (PDT) Received: from localhost.localdomain (c-71-234-172-214.hsd1.vt.comcast.net. [71.234.172.214]) by smtp.gmail.com with ESMTPSA id s127-v6sm12604251qkf.21.2018.05.22.18.18.38 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 May 2018 18:18:39 -0700 (PDT) X-EEMSG-check-009: 444-444 From: Kent Overstreet To: linux-kernel@vger.kernel.org, viro@zeniv.linux.org.uk, akpm@linux-foundation.org, willy@infradead.org, gregkh@linuxfoundation.org, linux-security-module@vger.kernel.org, selinux@tycho.nsa.gov, dev@openvswitch.org, shli@kernel.org, linux-raid@vger.kernel.org Date: Tue, 22 May 2018 21:18:16 -0400 Message-Id: <20180523011821.12165-1-kent.overstreet@gmail.com> X-Mailer: git-send-email 2.17.0 X-Mailman-Approved-At: Wed, 23 May 2018 08:03:44 -0400 Subject: [PATCH 1/6] Generic radix trees X-BeenThere: selinux@tycho.nsa.gov X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Security-Enhanced Linux \(SELinux\) mailing list" List-Post: List-Help: Cc: Kent Overstreet MIME-Version: 1.0 Errors-To: selinux-bounces@tycho.nsa.gov Sender: "Selinux" X-Virus-Scanned: ClamAV using ClamSMTP Very simple radix tree implementation that supports storing arbitrary size entries, up to PAGE_SIZE - upcoming patches will convert existing flex_array users to genradixes. The new genradix code has a much simpler API and implementation, and doesn't have a hard limit on the number of elements like flex_array does. Signed-off-by: Kent Overstreet --- include/linux/generic-radix-tree.h | 222 +++++++++++++++++++++++++++++ lib/Makefile | 3 +- lib/generic-radix-tree.c | 180 +++++++++++++++++++++++ 3 files changed, 404 insertions(+), 1 deletion(-) create mode 100644 include/linux/generic-radix-tree.h create mode 100644 lib/generic-radix-tree.c diff --git a/include/linux/generic-radix-tree.h b/include/linux/generic-radix-tree.h new file mode 100644 index 0000000000..3328813322 --- /dev/null +++ b/include/linux/generic-radix-tree.h @@ -0,0 +1,222 @@ +#ifndef _LINUX_GENERIC_RADIX_TREE_H +#define _LINUX_GENERIC_RADIX_TREE_H + +/* + * Generic radix trees/sparse arrays: + * + * Very simple and minimalistic, supporting arbitrary size entries up to + * PAGE_SIZE. + * + * A genradix is defined with the type it will store, like so: + * static GENRADIX(struct foo) foo_genradix; + * + * The main operations are: + * - genradix_init(radix) - initialize an empty genradix + * + * - genradix_free(radix) - free all memory owned by the genradix and + * reinitialize it + * + * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning + * NULL if that entry does not exist + * + * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry, + * allocating it if necessary + * + * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix + * + * The radix tree allocates one page of entries at a time, so entries may exist + * that were never explicitly allocated - they will be initialized to all + * zeroes. + * + * Internally, a genradix is just a radix tree of pages, and indexing works in + * terms of byte offsets. The wrappers in this header file use sizeof on the + * type the radix contains to calculate a byte offset from the index - see + * __idx_to_offset. + */ + +#include +#include +#include +#include + +struct genradix_node; + +struct __genradix { + struct genradix_node *root; + size_t depth; +}; + +#define __GENRADIX_INITIALIZER \ + { \ + .tree = { \ + .root = NULL, \ + .depth = 0, \ + } \ + } + +/* + * We use a 0 size array to stash the type we're storing without taking any + * space at runtime - then the various accessor macros can use typeof() to get + * to it for casts/sizeof - we also force the alignment so that storing a type + * with a ridiculous alignment doesn't blow up the alignment or size of the + * genradix. + */ + +#define GENRADIX(_type) \ +struct { \ + struct __genradix tree; \ + _type type[0] __aligned(1); \ +} + +#define DEFINE_GENRADIX(_name, _type) \ + GENRADIX(_type) _name = __GENRADIX_INITIALIZER + +/** + * genradix_init - initialize a genradix + * @_radix: genradix to initialize + * + * Does not fail + */ +#define genradix_init(_radix) \ +do { \ + *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \ +} while (0) + +void __genradix_free(struct __genradix *); + +/** + * genradix_free: free all memory owned by a genradix + * + * After freeing, @_radix will be reinitialized and empty + */ +#define genradix_free(_radix) __genradix_free(&(_radix)->tree) + +static inline size_t __idx_to_offset(size_t idx, size_t obj_size) +{ + if (__builtin_constant_p(obj_size)) + BUILD_BUG_ON(obj_size > PAGE_SIZE); + else + BUG_ON(obj_size > PAGE_SIZE); + + if (!is_power_of_2(obj_size)) { + size_t objs_per_page = PAGE_SIZE / obj_size; + + return (idx / objs_per_page) * PAGE_SIZE + + (idx % objs_per_page) * obj_size; + } else { + return idx * obj_size; + } +} + +#define __genradix_cast(_radix) (typeof((_radix)->type[0]) *) +#define __genradix_obj_size(_radix) sizeof((_radix)->type[0]) +#define __genradix_idx_to_offset(_radix, _idx) \ + __idx_to_offset(_idx, __genradix_obj_size(_radix)) + +void *__genradix_ptr(struct __genradix *, size_t); + +/** + * genradix_ptr - get a pointer to a genradix entry + * @_radix: genradix to access + * @_idx: index to fetch + * + * Returns a pointer to entry at @_idx, or NULL if that entry does not exist. + */ +#define genradix_ptr(_radix, _idx) \ + (__genradix_cast(_radix) \ + __genradix_ptr(&(_radix)->tree, \ + __genradix_idx_to_offset(_radix, _idx))) + +void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t); + +/** + * genradix_ptr - get a pointer to a genradix entry, allocating it if necessary + * @_radix: genradix to access + * @_idx: index to fetch + * @_gfp: gfp mask + * + * Returns a pointer to entry at @_idx, or NULL on allocation failure + */ +#define genradix_ptr_alloc(_radix, _idx, _gfp) \ + (__genradix_cast(_radix) \ + __genradix_ptr_alloc(&(_radix)->tree, \ + __genradix_idx_to_offset(_radix, _idx), \ + _gfp)) + +struct genradix_iter { + size_t offset; + size_t pos; +}; + +/** + * genradix_iter_init - initialize a genradix_iter + * @_radix: genradix that will be iterated over + * @_idx index to start iterating from + */ +#define genradix_iter_init(_radix, _idx) \ + ((struct genradix_iter) { \ + .pos = (_idx), \ + .offset = __genradix_idx_to_offset((_radix), (_idx)),\ + }) + +void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t); + +/** + * genradix_iter_peek - get first entry at or above iterator's current + * position + * @_iter: a genradix_iter + * @_radix: genradix being iterated over + * + * If no more entries exist at or above @_iter's current position, returns NULL + */ +#define genradix_iter_peek(_iter, _radix) \ + (__genradix_cast(_radix) \ + __genradix_iter_peek(_iter, &(_radix)->tree, \ + PAGE_SIZE / __genradix_obj_size(_radix))) + +static inline void __genradix_iter_advance(struct genradix_iter *iter, + size_t obj_size) +{ + iter->offset += obj_size; + + if (!is_power_of_2(obj_size) && + (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE) + iter->offset = round_up(iter->offset, PAGE_SIZE); + + iter->pos++; +} + +#define genradix_iter_advance(_iter, _radix) \ + __genradix_iter_advance(_iter, __genradix_obj_size(_radix)) + +/** + * genradix_for_each - iterate over entry in a genradix + * @_radix: genradix to iterate over + * @_iter: a genradix_iter to track current position + * @_p: pointer to genradix entry type + * + * On every iteration, @_p will point to the current entry, and @_iter.pos + * will be the current entry's index. + */ +#define genradix_for_each(_radix, _iter, _p) \ + for (_iter = genradix_iter_init(_radix, 0); \ + _p = genradix_iter_peek(&(_iter), _uradix); \ + genradix_iter_advance(&(_iter), _uradix)) + +int __genradix_prealloc(struct __genradix *, size_t, gfp_t); + +/** + * genradix_prealloc - preallocate entries in a generic radix tree + * @_radix: genradix to preallocate + * @_nr: number of entries to preallocate + * @_gfp: gfp mask + * + * Returns 0 on success, -ENOMEM on failure + */ +#define genradix_prealloc(_radix, _nr, _gfp) \ + __genradix_prealloc(&(_radix)->tree, \ + __genradix_idx_to_offset(_radix, _nr + 1),\ + _gfp) + + +#endif /* _LINUX_GENERIC_RADIX_TREE_H */ diff --git a/lib/Makefile b/lib/Makefile index a90d4fcd74..5db5a7fb1e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -39,7 +39,8 @@ obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \ gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ percpu-refcount.o percpu_ida.o rhashtable.o reciprocal_div.o \ - once.o refcount.o usercopy.o errseq.o bucket_locks.o + once.o refcount.o usercopy.o errseq.o bucket_locks.o \ + generic-radix-tree.o obj-$(CONFIG_STRING_SELFTEST) += test_string.o obj-y += string_helpers.o obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c new file mode 100644 index 0000000000..4537c7c62c --- /dev/null +++ b/lib/generic-radix-tree.c @@ -0,0 +1,180 @@ + +#include +#include +#include + +#define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *)) +#define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY) + +struct genradix_node { + union { + /* Interior node: */ + struct genradix_node *children[GENRADIX_ARY]; + + /* Leaf: */ + u8 data[PAGE_SIZE]; + }; +}; + +static inline unsigned genradix_depth_shift(unsigned depth) +{ + return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth; +} + +/* + * Returns size (of data, in bytes) that a tree of a given depth holds: + */ +static inline size_t genradix_depth_size(unsigned depth) +{ + return 1UL << genradix_depth_shift(depth); +} + +/* + * Returns pointer to the specified byte @offset within @radix, or NULL if not + * allocated + */ +void *__genradix_ptr(struct __genradix *radix, size_t offset) +{ + size_t level = radix->depth; + struct genradix_node *n = radix->root; + + if (offset >= genradix_depth_size(radix->depth)) + return NULL; + + while (1) { + if (!n) + return NULL; + if (!level) + break; + + level--; + + n = n->children[offset >> genradix_depth_shift(level)]; + offset &= genradix_depth_size(level) - 1; + } + + return &n->data[offset]; +} +EXPORT_SYMBOL(__genradix_ptr); + +/* + * Returns pointer to the specified byte @offset within @radix, allocating it if + * necessary - newly allocated slots are always zeroed out: + */ +void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, + gfp_t gfp_mask) +{ + struct genradix_node **n; + size_t level; + + /* Increase tree depth if necessary: */ + + while (offset >= genradix_depth_size(radix->depth)) { + struct genradix_node *new_root = + (void *) __get_free_page(gfp_mask|__GFP_ZERO); + + if (!new_root) + return NULL; + + new_root->children[0] = radix->root; + radix->root = new_root; + radix->depth++; + } + + n = &radix->root; + level = radix->depth; + + while (1) { + if (!*n) { + *n = (void *) __get_free_page(gfp_mask|__GFP_ZERO); + if (!*n) + return NULL; + } + + if (!level) + break; + + level--; + + n = &(*n)->children[offset >> genradix_depth_shift(level)]; + offset &= genradix_depth_size(level) - 1; + } + + return &(*n)->data[offset]; +} +EXPORT_SYMBOL(__genradix_ptr_alloc); + +void *__genradix_iter_peek(struct genradix_iter *iter, + struct __genradix *radix, + size_t objs_per_page) +{ + struct genradix_node *n; + size_t level, i; + + if (!radix->root) + return NULL; +restart: + if (iter->offset >= genradix_depth_size(radix->depth)) + return NULL; + + n = radix->root; + level = radix->depth; + + while (level) { + level--; + + i = (iter->offset >> genradix_depth_shift(level)) & + (GENRADIX_ARY - 1); + + while (!n->children[i]) { + i++; + iter->offset = round_down(iter->offset + + genradix_depth_size(level), + genradix_depth_size(level)); + iter->pos = (iter->offset >> PAGE_SHIFT) * + objs_per_page; + if (i == GENRADIX_ARY) + goto restart; + } + + n = n->children[i]; + } + + return &n->data[iter->offset & (PAGE_SIZE - 1)]; +} +EXPORT_SYMBOL(__genradix_iter_peek); + +static void genradix_free_recurse(struct genradix_node *n, unsigned level) +{ + if (level) { + unsigned i; + + for (i = 0; i < GENRADIX_ARY; i++) + if (n->children[i]) + genradix_free_recurse(n->children[i], level - 1); + } + + free_page((unsigned long) n); +} + +int __genradix_prealloc(struct __genradix *radix, size_t size, + gfp_t gfp_mask) +{ + size_t offset; + + for (offset = 0; offset < size; offset += PAGE_SIZE) + if (!__genradix_ptr_alloc(radix, offset, gfp_mask)) + return -ENOMEM; + + return 0; +} +EXPORT_SYMBOL(__genradix_prealloc); + +void __genradix_free(struct __genradix *radix) +{ + genradix_free_recurse(radix->root, radix->depth); + + radix->root = NULL; + radix->depth = 0; +} +EXPORT_SYMBOL(__genradix_free);