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 * @returns
78 * The jenkins hash for this data.
79 */
80 static inline uint32_t
os_hash_jenkins(const void * data,size_t length)81 os_hash_jenkins(const void *data, size_t length)
82 {
83 return os_hash_jenkins_finish(os_hash_jenkins_update(data, length, 0));
84 }
85
86 /*!
87 * @function os_hash_kernel_pointer
88 *
89 * @brief
90 * Hashes a pointer from a zone.
91 *
92 * @discussion
93 * This is a really cheap and fast hash that will behave well for pointers
94 * allocated by the kernel.
95 *
96 * This should be not used for untrusted pointer values from userspace,
97 * or cases when the pointer is somehow under the control of userspace.
98 *
99 * This hash function utilizes knowledge about the span of the kernel
100 * address space and inherent alignment of zalloc/kalloc.
101 *
102 * @param pointer
103 * The pointer to hash.
104 *
105 * @returns
106 * The hash for this pointer.
107 */
108 static inline uint32_t
os_hash_kernel_pointer(const void * pointer)109 os_hash_kernel_pointer(const void *pointer)
110 {
111 uintptr_t key = (uintptr_t)pointer >> 4;
112 key *= 0x5052acdb;
113 return (uint32_t)key ^ __builtin_bswap32((uint32_t)key);
114 }
115
116 __END_DECLS
117
118 #endif // PRIVATE
119 #endif // _OS_HASH_H_
120