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