fs/f2fs/hash.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * fs/f2fs/hash.c
   4  *
   5  * Copyright (c) 2012 Samsung Electronics Co., Ltd.
   6  *             http://www.samsung.com/
   7  *
   8  * Portions of this code from linux/fs/ext3/hash.c
   9  *
  10  * Copyright (C) 2002 by Theodore Ts'o
  11  */
  12 #include <linux/types.h>
  13 #include <linux/fs.h>
  14 #include <linux/f2fs_fs.h>
  15 #include <linux/pagemap.h>
  16 #include <linux/unicode.h>
  17
  18 #include "f2fs.h"
  19
  20 /*
  21  * Hashing code copied from ext3
  22  */
  23 #define DELTA 0x9E3779B9
  24
  25 static void TEA_transform(unsigned int buf[4], unsigned int const in[])
  26 {
  27         __u32 sum = 0;
  28         __u32 b0 = buf[0], b1 = buf[1];
  29         __u32 a = in[0], b = in[1], c = in[2], d = in[3];
  30         int n = 16;
  31
  32         do {
  33                 sum += DELTA;
  34                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  35                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  36         } while (--n);
  37
  38         buf[0] += b0;
  39         buf[1] += b1;
  40 }
  41
  42 static void str2hashbuf(const unsigned char *msg, size_t len,
  43                                 unsigned int *buf, int num)
  44 {
  45         unsigned pad, val;
  46         int i;
  47
  48         pad = (__u32)len | ((__u32)len << 8);
  49         pad |= pad << 16;
  50
  51         val = pad;
  52         if (len > num * 4)
  53                 len = num * 4;
  54         for (i = 0; i < len; i++) {
  55                 if ((i % 4) == 0)
  56                         val = pad;
  57                 val = msg[i] + (val << 8);
  58                 if ((i % 4) == 3) {
  59                         *buf++ = val;
  60                         val = pad;
  61                         num--;
  62                 }
  63         }
  64         if (--num >= 0)
  65                 *buf++ = val;
  66         while (--num >= 0)
  67                 *buf++ = pad;
  68 }
  69
  70 static u32 TEA_hash_name(const u8 *p, size_t len)
  71 {
  72         __u32 in[8], buf[4];
  73
  74         /* Initialize the default seed for the hash checksum functions */
  75         buf[0] = 0x67452301;
  76         buf[1] = 0xefcdab89;
  77         buf[2] = 0x98badcfe;
  78         buf[3] = 0x10325476;
  79
  80         while (1) {
  81                 str2hashbuf(p, len, in, 4);
  82                 TEA_transform(buf, in);
  83                 p += 16;
  84                 if (len <= 16)
  85                         break;
  86                 len -= 16;
  87         }
  88         return buf[0] & ~F2FS_HASH_COL_BIT;
  89 }
  90
  91 /*
  92  * Compute @fname->hash.  For all directories, @fname->disk_name must be set.
  93  * For casefolded directories, @fname->usr_fname must be set, and also
  94  * @fname->cf_name if the filename is valid Unicode and is not "." or "..".
  95  */
  96 void f2fs_hash_filename(const struct inode *dir, struct f2fs_filename *fname)
  97 {
  98         const u8 *name = fname->disk_name.name;
  99         size_t len = fname->disk_name.len;
 100
 101         WARN_ON_ONCE(!name);
 102
 103         if (is_dot_dotdot(name, len)) {
 104                 fname->hash = 0;
 105                 return;
 106         }
 107
 108 #if IS_ENABLED(CONFIG_UNICODE)
 109         if (IS_CASEFOLDED(dir)) {
 110                 /*
 111                  * If the casefolded name is provided, hash it instead of the
 112                  * on-disk name.  If the casefolded name is *not* provided, that
 113                  * should only be because the name wasn't valid Unicode or was
 114                  * "." or "..", so fall back to treating the name as an opaque
 115                  * byte sequence.  Note that to handle encrypted directories,
 116                  * the fallback must use usr_fname (plaintext) rather than
 117                  * disk_name (ciphertext).
 118                  */
 119                 WARN_ON_ONCE(!fname->usr_fname->name);
 120                 if (fname->cf_name.name) {
 121                         name = fname->cf_name.name;
 122                         len = fname->cf_name.len;
 123                 } else {
 124                         name = fname->usr_fname->name;
 125                         len = fname->usr_fname->len;
 126                 }
 127                 if (IS_ENCRYPTED(dir)) {
 128                         struct qstr tmp = QSTR_INIT(name, len);
 129
 130                         fname->hash =
 131                                 cpu_to_le32(fscrypt_fname_siphash(dir, &tmp));
 132                         return;
 133                 }
 134         }
 135 #endif
 136         fname->hash = cpu_to_le32(TEA_hash_name(name, len));
 137 }