LCOV - code coverage report
Current view: top level - fs/ext4 - hash.c (source / functions) Hit Total Coverage
Test: combined.info Lines: 84 146 57.5 %
Date: 2022-04-01 14:17:54 Functions: 4 6 66.7 %
Branches: 15 45 33.3 %

           Branch data     Line data    Source code
       1                 :            : // SPDX-License-Identifier: GPL-2.0
       2                 :            : /*
       3                 :            :  *  linux/fs/ext4/hash.c
       4                 :            :  *
       5                 :            :  * Copyright (C) 2002 by Theodore Ts'o
       6                 :            :  */
       7                 :            : 
       8                 :            : #include <linux/fs.h>
       9                 :            : #include <linux/unicode.h>
      10                 :            : #include <linux/compiler.h>
      11                 :            : #include <linux/bitops.h>
      12                 :            : #include "ext4.h"
      13                 :            : 
      14                 :            : #define DELTA 0x9E3779B9
      15                 :            : 
      16                 :          0 : static void TEA_transform(__u32 buf[4], __u32 const in[])
      17                 :            : {
      18                 :          0 :         __u32   sum = 0;
      19                 :          0 :         __u32   b0 = buf[0], b1 = buf[1];
      20                 :          0 :         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
      21                 :          0 :         int     n = 16;
      22                 :            : 
      23                 :          0 :         do {
      24                 :          0 :                 sum += DELTA;
      25                 :          0 :                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
      26                 :          0 :                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
      27         [ #  # ]:          0 :         } while (--n);
      28                 :            : 
      29                 :          0 :         buf[0] += b0;
      30                 :          0 :         buf[1] += b1;
      31                 :          0 : }
      32                 :            : 
      33                 :            : /* F, G and H are basic MD4 functions: selection, majority, parity */
      34                 :            : #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
      35                 :            : #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
      36                 :            : #define H(x, y, z) ((x) ^ (y) ^ (z))
      37                 :            : 
      38                 :            : /*
      39                 :            :  * The generic round function.  The application is so specific that
      40                 :            :  * we don't bother protecting all the arguments with parens, as is generally
      41                 :            :  * good macro practice, in favor of extra legibility.
      42                 :            :  * Rotation is separate from addition to prevent recomputation
      43                 :            :  */
      44                 :            : #define ROUND(f, a, b, c, d, x, s)      \
      45                 :            :         (a += f(b, c, d) + x, a = rol32(a, s))
      46                 :            : #define K1 0
      47                 :            : #define K2 013240474631UL
      48                 :            : #define K3 015666365641UL
      49                 :            : 
      50                 :            : /*
      51                 :            :  * Basic cut-down MD4 transform.  Returns only 32 bits of result.
      52                 :            :  */
      53                 :      15685 : static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
      54                 :            : {
      55                 :      15685 :         __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
      56                 :            : 
      57                 :            :         /* Round 1 */
      58                 :      15685 :         ROUND(F, a, b, c, d, in[0] + K1,  3);
      59                 :      15685 :         ROUND(F, d, a, b, c, in[1] + K1,  7);
      60                 :      15685 :         ROUND(F, c, d, a, b, in[2] + K1, 11);
      61                 :      15685 :         ROUND(F, b, c, d, a, in[3] + K1, 19);
      62                 :      15685 :         ROUND(F, a, b, c, d, in[4] + K1,  3);
      63                 :      15685 :         ROUND(F, d, a, b, c, in[5] + K1,  7);
      64                 :      15685 :         ROUND(F, c, d, a, b, in[6] + K1, 11);
      65                 :      15685 :         ROUND(F, b, c, d, a, in[7] + K1, 19);
      66                 :            : 
      67                 :            :         /* Round 2 */
      68                 :      15685 :         ROUND(G, a, b, c, d, in[1] + K2,  3);
      69                 :      15685 :         ROUND(G, d, a, b, c, in[3] + K2,  5);
      70                 :      15685 :         ROUND(G, c, d, a, b, in[5] + K2,  9);
      71                 :      15685 :         ROUND(G, b, c, d, a, in[7] + K2, 13);
      72                 :      15685 :         ROUND(G, a, b, c, d, in[0] + K2,  3);
      73                 :      15685 :         ROUND(G, d, a, b, c, in[2] + K2,  5);
      74                 :      15685 :         ROUND(G, c, d, a, b, in[4] + K2,  9);
      75                 :      15685 :         ROUND(G, b, c, d, a, in[6] + K2, 13);
      76                 :            : 
      77                 :            :         /* Round 3 */
      78                 :      15685 :         ROUND(H, a, b, c, d, in[3] + K3,  3);
      79                 :      15685 :         ROUND(H, d, a, b, c, in[7] + K3,  9);
      80                 :      15685 :         ROUND(H, c, d, a, b, in[2] + K3, 11);
      81                 :      15685 :         ROUND(H, b, c, d, a, in[6] + K3, 15);
      82                 :      15685 :         ROUND(H, a, b, c, d, in[1] + K3,  3);
      83                 :      15685 :         ROUND(H, d, a, b, c, in[5] + K3,  9);
      84                 :      15685 :         ROUND(H, c, d, a, b, in[0] + K3, 11);
      85                 :      15685 :         ROUND(H, b, c, d, a, in[4] + K3, 15);
      86                 :            : 
      87                 :      15685 :         buf[0] += a;
      88                 :      15685 :         buf[1] += b;
      89                 :      15685 :         buf[2] += c;
      90                 :      15685 :         buf[3] += d;
      91                 :            : 
      92                 :      15685 :         return buf[1]; /* "most hashed" word */
      93                 :            : }
      94                 :            : #undef ROUND
      95                 :            : #undef K1
      96                 :            : #undef K2
      97                 :            : #undef K3
      98                 :            : #undef F
      99                 :            : #undef G
     100                 :            : #undef H
     101                 :            : 
     102                 :            : /* The old legacy hash */
     103                 :            : static __u32 dx_hack_hash_unsigned(const char *name, int len)
     104                 :            : {
     105                 :            :         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
     106                 :            :         const unsigned char *ucp = (const unsigned char *) name;
     107                 :            : 
     108         [ #  # ]:          0 :         while (len--) {
     109                 :          0 :                 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
     110                 :            : 
     111         [ #  # ]:          0 :                 if (hash & 0x80000000)
     112                 :          0 :                         hash -= 0x7fffffff;
     113                 :            :                 hash1 = hash0;
     114                 :            :                 hash0 = hash;
     115                 :            :         }
     116                 :          0 :         return hash0 << 1;
     117                 :            : }
     118                 :            : 
     119                 :            : static __u32 dx_hack_hash_signed(const char *name, int len)
     120                 :            : {
     121                 :            :         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
     122                 :            :         const signed char *scp = (const signed char *) name;
     123                 :            : 
     124         [ #  # ]:          0 :         while (len--) {
     125                 :          0 :                 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
     126                 :            : 
     127         [ #  # ]:          0 :                 if (hash & 0x80000000)
     128                 :          0 :                         hash -= 0x7fffffff;
     129                 :            :                 hash1 = hash0;
     130                 :            :                 hash0 = hash;
     131                 :            :         }
     132                 :          0 :         return hash0 << 1;
     133                 :            : }
     134                 :            : 
     135                 :      15685 : static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
     136                 :            : {
     137                 :      15685 :         __u32   pad, val;
     138                 :      15685 :         int     i;
     139                 :      15685 :         const signed char *scp = (const signed char *) msg;
     140                 :            : 
     141                 :      15685 :         pad = (__u32)len | ((__u32)len << 8);
     142                 :      15685 :         pad |= pad << 16;
     143                 :            : 
     144                 :      15685 :         val = pad;
     145                 :      15685 :         if (len > num*4)
     146                 :            :                 len = num * 4;
     147         [ +  + ]:     286867 :         for (i = 0; i < len; i++) {
     148                 :     271182 :                 val = ((int) scp[i]) + (val << 8);
     149         [ +  + ]:     271182 :                 if ((i % 4) == 3) {
     150                 :      63249 :                         *buf++ = val;
     151                 :      63249 :                         val = pad;
     152                 :      63249 :                         num--;
     153                 :            :                 }
     154                 :            :         }
     155         [ +  + ]:      15685 :         if (--num >= 0)
     156                 :      13089 :                 *buf++ = val;
     157         [ +  + ]:      64827 :         while (--num >= 0)
     158                 :      49142 :                 *buf++ = pad;
     159                 :      15685 : }
     160                 :            : 
     161                 :          0 : static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
     162                 :            : {
     163                 :          0 :         __u32   pad, val;
     164                 :          0 :         int     i;
     165                 :          0 :         const unsigned char *ucp = (const unsigned char *) msg;
     166                 :            : 
     167                 :          0 :         pad = (__u32)len | ((__u32)len << 8);
     168                 :          0 :         pad |= pad << 16;
     169                 :            : 
     170                 :          0 :         val = pad;
     171                 :          0 :         if (len > num*4)
     172                 :            :                 len = num * 4;
     173         [ #  # ]:          0 :         for (i = 0; i < len; i++) {
     174                 :          0 :                 val = ((int) ucp[i]) + (val << 8);
     175         [ #  # ]:          0 :                 if ((i % 4) == 3) {
     176                 :          0 :                         *buf++ = val;
     177                 :          0 :                         val = pad;
     178                 :          0 :                         num--;
     179                 :            :                 }
     180                 :            :         }
     181         [ #  # ]:          0 :         if (--num >= 0)
     182                 :          0 :                 *buf++ = val;
     183         [ #  # ]:          0 :         while (--num >= 0)
     184                 :          0 :                 *buf++ = pad;
     185                 :          0 : }
     186                 :            : 
     187                 :            : /*
     188                 :            :  * Returns the hash of a filename.  If len is 0 and name is NULL, then
     189                 :            :  * this function can be used to test whether or not a hash version is
     190                 :            :  * supported.
     191                 :            :  *
     192                 :            :  * The seed is an 4 longword (32 bits) "secret" which can be used to
     193                 :            :  * uniquify a hash.  If the seed is all zero's, then some default seed
     194                 :            :  * may be used.
     195                 :            :  *
     196                 :            :  * A particular hash version specifies whether or not the seed is
     197                 :            :  * represented, and whether or not the returned hash is 32 bits or 64
     198                 :            :  * bits.  32 bit hashes will return 0 for the minor hash.
     199                 :            :  */
     200                 :      14200 : static int __ext4fs_dirhash(const char *name, int len,
     201                 :            :                             struct dx_hash_info *hinfo)
     202                 :            : {
     203                 :      14200 :         __u32   hash;
     204                 :      14200 :         __u32   minor_hash = 0;
     205                 :      14200 :         const char      *p;
     206                 :      14200 :         int             i;
     207                 :      14200 :         __u32           in[8], buf[4];
     208                 :      14200 :         void            (*str2hashbuf)(const char *, int, __u32 *, int) =
     209                 :            :                                 str2hashbuf_signed;
     210                 :            : 
     211                 :            :         /* Initialize the default seed for the hash checksum functions */
     212                 :      14200 :         buf[0] = 0x67452301;
     213                 :      14200 :         buf[1] = 0xefcdab89;
     214                 :      14200 :         buf[2] = 0x98badcfe;
     215                 :      14200 :         buf[3] = 0x10325476;
     216                 :            : 
     217                 :            :         /* Check to see if the seed is all zero's */
     218         [ +  - ]:      14200 :         if (hinfo->seed) {
     219         [ +  - ]:      14200 :                 for (i = 0; i < 4; i++) {
     220         [ +  - ]:      14200 :                         if (hinfo->seed[i]) {
     221                 :      14200 :                                 memcpy(buf, hinfo->seed, sizeof(buf));
     222                 :      14200 :                                 break;
     223                 :            :                         }
     224                 :            :                 }
     225                 :            :         }
     226                 :            : 
     227   [ -  -  -  +  :      14200 :         switch (hinfo->hash_version) {
                -  -  - ]
     228                 :            :         case DX_HASH_LEGACY_UNSIGNED:
     229                 :            :                 hash = dx_hack_hash_unsigned(name, len);
     230                 :          0 :                 break;
     231                 :            :         case DX_HASH_LEGACY:
     232                 :            :                 hash = dx_hack_hash_signed(name, len);
     233                 :          0 :                 break;
     234                 :          0 :         case DX_HASH_HALF_MD4_UNSIGNED:
     235                 :          0 :                 str2hashbuf = str2hashbuf_unsigned;
     236                 :            :                 /* fall through */
     237                 :      14200 :         case DX_HASH_HALF_MD4:
     238                 :      14200 :                 p = name;
     239         [ +  + ]:      29885 :                 while (len > 0) {
     240                 :      15685 :                         (*str2hashbuf)(p, len, in, 8);
     241                 :      15685 :                         half_md4_transform(buf, in);
     242                 :      15685 :                         len -= 32;
     243                 :      15685 :                         p += 32;
     244                 :            :                 }
     245                 :      14200 :                 minor_hash = buf[2];
     246                 :      14200 :                 hash = buf[1];
     247                 :      14200 :                 break;
     248                 :          0 :         case DX_HASH_TEA_UNSIGNED:
     249                 :          0 :                 str2hashbuf = str2hashbuf_unsigned;
     250                 :            :                 /* fall through */
     251                 :          0 :         case DX_HASH_TEA:
     252                 :          0 :                 p = name;
     253         [ #  # ]:          0 :                 while (len > 0) {
     254                 :          0 :                         (*str2hashbuf)(p, len, in, 4);
     255                 :          0 :                         TEA_transform(buf, in);
     256                 :          0 :                         len -= 16;
     257                 :          0 :                         p += 16;
     258                 :            :                 }
     259                 :          0 :                 hash = buf[0];
     260                 :          0 :                 minor_hash = buf[1];
     261                 :          0 :                 break;
     262                 :          0 :         default:
     263                 :          0 :                 hinfo->hash = 0;
     264                 :          0 :                 return -1;
     265                 :            :         }
     266                 :      14200 :         hash = hash & ~1;
     267         [ -  + ]:      14200 :         if (hash == (EXT4_HTREE_EOF_32BIT << 1))
     268                 :          0 :                 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
     269                 :      14200 :         hinfo->hash = hash;
     270                 :      14200 :         hinfo->minor_hash = minor_hash;
     271                 :      14200 :         return 0;
     272                 :            : }
     273                 :            : 
     274                 :      14200 : int ext4fs_dirhash(const struct inode *dir, const char *name, int len,
     275                 :            :                    struct dx_hash_info *hinfo)
     276                 :            : {
     277                 :            : #ifdef CONFIG_UNICODE
     278                 :            :         const struct unicode_map *um = EXT4_SB(dir->i_sb)->s_encoding;
     279                 :            :         int r, dlen;
     280                 :            :         unsigned char *buff;
     281                 :            :         struct qstr qstr = {.name = name, .len = len };
     282                 :            : 
     283                 :            :         if (len && IS_CASEFOLDED(dir) && um) {
     284                 :            :                 buff = kzalloc(sizeof(char) * PATH_MAX, GFP_KERNEL);
     285                 :            :                 if (!buff)
     286                 :            :                         return -ENOMEM;
     287                 :            : 
     288                 :            :                 dlen = utf8_casefold(um, &qstr, buff, PATH_MAX);
     289                 :            :                 if (dlen < 0) {
     290                 :            :                         kfree(buff);
     291                 :            :                         goto opaque_seq;
     292                 :            :                 }
     293                 :            : 
     294                 :            :                 r = __ext4fs_dirhash(buff, dlen, hinfo);
     295                 :            : 
     296                 :            :                 kfree(buff);
     297                 :            :                 return r;
     298                 :            :         }
     299                 :            : opaque_seq:
     300                 :            : #endif
     301                 :      14200 :         return __ext4fs_dirhash(name, len, hinfo);
     302                 :            : }

Generated by: LCOV version 1.14