fs/f2fs/hash.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * fs/f2fs/hash.c
0004  *
0005  * Copyright (c) 2012 Samsung Electronics Co., Ltd.
0006  *             http://www.samsung.com/
0007  *
0008  * Portions of this code from linux/fs/ext3/hash.c
0009  *
0010  * Copyright (C) 2002 by Theodore Ts'o
0011  */
0012 #include <linux/types.h>
0013 #include <linux/fs.h>
0014 #include <linux/f2fs_fs.h>
0015 #include <linux/pagemap.h>
0016 #include <linux/unicode.h>
0017
0018 #include "f2fs.h"
0019
0020 /*
0021  * Hashing code copied from ext3
0022  */
0023 #define DELTA 0x9E3779B9
0024
0025 static void TEA_transform(unsigned int buf[4], unsigned int const in[])
0026 {
0027     __u32 sum = 0;
0028     __u32 b0 = buf[0], b1 = buf[1];
0029     __u32 a = in[0], b = in[1], c = in[2], d = in[3];
0030     int n = 16;
0031
0032     do {
0033         sum += DELTA;
0034         b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
0035         b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
0036     } while (--n);
0037
0038     buf[0] += b0;
0039     buf[1] += b1;
0040 }
0041
0042 static void str2hashbuf(const unsigned char *msg, size_t len,
0043                 unsigned int *buf, int num)
0044 {
0045     unsigned pad, val;
0046     int i;
0047
0048     pad = (__u32)len | ((__u32)len << 8);
0049     pad |= pad << 16;
0050
0051     val = pad;
0052     if (len > num * 4)
0053         len = num * 4;
0054     for (i = 0; i < len; i++) {
0055         if ((i % 4) == 0)
0056             val = pad;
0057         val = msg[i] + (val << 8);
0058         if ((i % 4) == 3) {
0059             *buf++ = val;
0060             val = pad;
0061             num--;
0062         }
0063     }
0064     if (--num >= 0)
0065         *buf++ = val;
0066     while (--num >= 0)
0067         *buf++ = pad;
0068 }
0069
0070 static u32 TEA_hash_name(const u8 *p, size_t len)
0071 {
0072     __u32 in[8], buf[4];
0073
0074     /* Initialize the default seed for the hash checksum functions */
0075     buf[0] = 0x67452301;
0076     buf[1] = 0xefcdab89;
0077     buf[2] = 0x98badcfe;
0078     buf[3] = 0x10325476;
0079
0080     while (1) {
0081         str2hashbuf(p, len, in, 4);
0082         TEA_transform(buf, in);
0083         p += 16;
0084         if (len <= 16)
0085             break;
0086         len -= 16;
0087     }
0088     return buf[0] & ~F2FS_HASH_COL_BIT;
0089 }
0090
0091 /*
0092  * Compute @fname->hash.  For all directories, @fname->disk_name must be set.
0093  * For casefolded directories, @fname->usr_fname must be set, and also
0094  * @fname->cf_name if the filename is valid Unicode and is not "." or "..".
0095  */
0096 void f2fs_hash_filename(const struct inode *dir, struct f2fs_filename *fname)
0097 {
0098     const u8 *name = fname->disk_name.name;
0099     size_t len = fname->disk_name.len;
0100
0101     WARN_ON_ONCE(!name);
0102
0103     if (is_dot_dotdot(name, len)) {
0104         fname->hash = 0;
0105         return;
0106     }
0107
0108 #if IS_ENABLED(CONFIG_UNICODE)
0109     if (IS_CASEFOLDED(dir)) {
0110         /*
0111          * If the casefolded name is provided, hash it instead of the
0112          * on-disk name.  If the casefolded name is *not* provided, that
0113          * should only be because the name wasn't valid Unicode or was
0114          * "." or "..", so fall back to treating the name as an opaque
0115          * byte sequence.  Note that to handle encrypted directories,
0116          * the fallback must use usr_fname (plaintext) rather than
0117          * disk_name (ciphertext).
0118          */
0119         WARN_ON_ONCE(!fname->usr_fname->name);
0120         if (fname->cf_name.name) {
0121             name = fname->cf_name.name;
0122             len = fname->cf_name.len;
0123         } else {
0124             name = fname->usr_fname->name;
0125             len = fname->usr_fname->len;
0126         }
0127         if (IS_ENCRYPTED(dir)) {
0128             struct qstr tmp = QSTR_INIT(name, len);
0129
0130             fname->hash =
0131                 cpu_to_le32(fscrypt_fname_siphash(dir, &tmp));
0132             return;
0133         }
0134     }
0135 #endif
0136     fname->hash = cpu_to_le32(TEA_hash_name(name, len));
0137 }