1 /*
2 * Copyright (c) 2018 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #ifndef _OS_HASH_H_
30 #define _OS_HASH_H_
31 #if PRIVATE
32
33 #include <os/base.h>
34
35 __BEGIN_DECLS
36
37 static inline uint32_t
os_hash_jenkins_update(const void * data,size_t length,uint32_t hash)38 os_hash_jenkins_update(const void *data, size_t length, uint32_t hash)
39 {
40 const uint8_t *key = (const uint8_t *)data;
41
42 for (size_t i = 0; i < length; i++) {
43 hash += key[i];
44 hash += (hash << 10);
45 hash ^= (hash >> 6);
46 }
47
48 return hash;
49 }
50
51 static inline uint32_t
os_hash_jenkins_finish(uint32_t hash)52 os_hash_jenkins_finish(uint32_t hash)
53 {
54 hash += (hash << 3);
55 hash ^= (hash >> 11);
56 hash += (hash << 15);
57
58 return hash;
59 }
60
61 /*!
62 * @function os_hash_jenkins
63 *
64 * @brief
65 * The original Jenkins "one at a time" hash.
66 *
67 * @discussion
68 * TBD: There may be some value to unrolling here,
69 * depending on the architecture.
70 *
71 * @param data
72 * The address of the data to hash.
73 *
74 * @param length
75 * The length of the data to hash
76 *
77 * @param seed
78 * An optional hash seed (defaults to 0).
79 *
80 * @returns
81 * The jenkins hash for this data.
82 */
83 __attribute__((overloadable))
84 static inline uint32_t
os_hash_jenkins(const void * data,size_t length,uint32_t seed)85 os_hash_jenkins(const void *data, size_t length, uint32_t seed)
86 {
87 return os_hash_jenkins_finish(os_hash_jenkins_update(data, length, seed));
88 }
89
90 __attribute__((overloadable))
91 static inline uint32_t
os_hash_jenkins(const void * data,size_t length)92 os_hash_jenkins(const void *data, size_t length)
93 {
94 return os_hash_jenkins(data, length, 0);
95 }
96
97 /*!
98 * @function os_hash_kernel_pointer
99 *
100 * @brief
101 * Hashes a pointer from a zone.
102 *
103 * @discussion
104 * This is a really cheap and fast hash that will behave well for pointers
105 * allocated by the kernel.
106 *
107 * This should be not used for untrusted pointer values from userspace,
108 * or cases when the pointer is somehow under the control of userspace.
109 *
110 * This hash function utilizes knowledge about the span of the kernel
111 * address space and inherent alignment of zalloc/kalloc.
112 *
113 * @param pointer
114 * The pointer to hash.
115 *
116 * @returns
117 * The hash for this pointer.
118 */
119 static inline uint32_t
os_hash_kernel_pointer(const void * pointer)120 os_hash_kernel_pointer(const void *pointer)
121 {
122 uintptr_t key = (uintptr_t)pointer >> 4;
123 key *= 0x5052acdb;
124 return (uint32_t)key ^ __builtin_bswap32((uint32_t)key);
125 }
126
127 __END_DECLS
128
129 #endif // PRIVATE
130 #endif // _OS_HASH_H_
131