Branch data     Line data    Source code

       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/cryptohash.h>
      16                 :            : #include <linux/pagemap.h>
      17                 :            : #include <linux/unicode.h>
      18                 :            : 
      19                 :            : #include "f2fs.h"
      20                 :            : 
      21                 :            : /*
      22                 :            :  * Hashing code copied from ext3
      23                 :            :  */
      24                 :            : #define DELTA 0x9E3779B9
      25                 :            : 
      26                 :          0 : static void TEA_transform(unsigned int buf[4], unsigned int const in[])
      27                 :            : {
      28                 :            :         __u32 sum = 0;
      29                 :          0 :         __u32 b0 = buf[0], b1 = buf[1];
      30                 :          0 :         __u32 a = in[0], b = in[1], c = in[2], d = in[3];
      31                 :            :         int n = 16;
      32                 :            : 
      33                 :            :         do {
      34                 :          0 :                 sum += DELTA;
      35                 :          0 :                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
      36                 :          0 :                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
      37         [ #  # ]:          0 :         } while (--n);
      38                 :            : 
      39                 :          0 :         buf[0] += b0;
      40                 :          0 :         buf[1] += b1;
      41                 :          0 : }
      42                 :            : 
      43                 :          0 : static void str2hashbuf(const unsigned char *msg, size_t len,
      44                 :            :                                 unsigned int *buf, int num)
      45                 :            : {
      46                 :            :         unsigned pad, val;
      47                 :            :         int i;
      48                 :            : 
      49                 :          0 :         pad = (__u32)len | ((__u32)len << 8);
      50                 :          0 :         pad |= pad << 16;
      51                 :            : 
      52                 :            :         val = pad;
      53         [ #  # ]:          0 :         if (len > num * 4)
      54                 :            :                 len = num * 4;
      55         [ #  # ]:          0 :         for (i = 0; i < len; i++) {
      56         [ #  # ]:          0 :                 if ((i % 4) == 0)
      57                 :            :                         val = pad;
      58                 :          0 :                 val = msg[i] + (val << 8);
      59         [ #  # ]:          0 :                 if ((i % 4) == 3) {
      60                 :          0 :                         *buf++ = val;
      61                 :            :                         val = pad;
      62                 :          0 :                         num--;
      63                 :            :                 }
      64                 :            :         }
      65         [ #  # ]:          0 :         if (--num >= 0)
      66                 :          0 :                 *buf++ = val;
      67         [ #  # ]:          0 :         while (--num >= 0)
      68                 :          0 :                 *buf++ = pad;
      69                 :          0 : }
      70                 :            : 
      71                 :          0 : static f2fs_hash_t __f2fs_dentry_hash(const struct qstr *name_info,
      72                 :            :                                 struct fscrypt_name *fname)
      73                 :            : {
      74                 :            :         __u32 hash;
      75                 :            :         f2fs_hash_t f2fs_hash;
      76                 :            :         const unsigned char *p;
      77                 :            :         __u32 in[8], buf[4];
      78                 :          0 :         const unsigned char *name = name_info->name;
      79                 :          0 :         size_t len = name_info->len;
      80                 :            : 
      81                 :            :         /* encrypted bigname case */
      82   [ #  #  #  # ]:          0 :         if (fname && !fname->disk_name.name)
      83                 :          0 :                 return cpu_to_le32(fname->hash);
      84                 :            : 
      85         [ #  # ]:          0 :         if (is_dot_dotdot(name_info))
      86                 :            :                 return 0;
      87                 :            : 
      88                 :            :         /* Initialize the default seed for the hash checksum functions */
      89                 :          0 :         buf[0] = 0x67452301;
      90                 :          0 :         buf[1] = 0xefcdab89;
      91                 :          0 :         buf[2] = 0x98badcfe;
      92                 :          0 :         buf[3] = 0x10325476;
      93                 :            : 
      94                 :            :         p = name;
      95                 :            :         while (1) {
      96                 :          0 :                 str2hashbuf(p, len, in, 4);
      97                 :          0 :                 TEA_transform(buf, in);
      98                 :          0 :                 p += 16;
      99         [ #  # ]:          0 :                 if (len <= 16)
     100                 :            :                         break;
     101                 :          0 :                 len -= 16;
     102                 :          0 :         }
     103                 :          0 :         hash = buf[0];
     104                 :            :         f2fs_hash = cpu_to_le32(hash & ~F2FS_HASH_COL_BIT);
     105                 :          0 :         return f2fs_hash;
     106                 :            : }
     107                 :            : 
     108                 :          0 : f2fs_hash_t f2fs_dentry_hash(const struct inode *dir,
     109                 :            :                 const struct qstr *name_info, struct fscrypt_name *fname)
     110                 :            : {
     111                 :            : #ifdef CONFIG_UNICODE
     112                 :            :         struct f2fs_sb_info *sbi = F2FS_SB(dir->i_sb);
     113                 :            :         const struct unicode_map *um = sbi->s_encoding;
     114                 :            :         int r, dlen;
     115                 :            :         unsigned char *buff;
     116                 :            :         struct qstr folded;
     117                 :            : 
     118                 :            :         if (!name_info->len || !IS_CASEFOLDED(dir))
     119                 :            :                 goto opaque_seq;
     120                 :            : 
     121                 :            :         buff = f2fs_kzalloc(sbi, sizeof(char) * PATH_MAX, GFP_KERNEL);
     122                 :            :         if (!buff)
     123                 :            :                 return -ENOMEM;
     124                 :            : 
     125                 :            :         dlen = utf8_casefold(um, name_info, buff, PATH_MAX);
     126                 :            :         if (dlen < 0) {
     127                 :            :                 kvfree(buff);
     128                 :            :                 goto opaque_seq;
     129                 :            :         }
     130                 :            :         folded.name = buff;
     131                 :            :         folded.len = dlen;
     132                 :            :         r = __f2fs_dentry_hash(&folded, fname);
     133                 :            : 
     134                 :            :         kvfree(buff);
     135                 :            :         return r;
     136                 :            : 
     137                 :            : opaque_seq:
     138                 :            : #endif
     139                 :          0 :         return __f2fs_dentry_hash(name_info, fname);
     140                 :            : }