projects / apple / xnu.git / blame
| Commit | Line | Data |
|---|---|---|
| 0a7de745 A |
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 | /*! | |
| 38 | * @function os_hash_jenkins | |
| 39 | * | |
| 40 | * @brief | |
| 41 | * The original Jenkins "one at a time" hash. | |
| 42 | * | |
| 43 | * @discussion | |
| 44 | * TBD: There may be some value to unrolling here, | |
| 45 | * depending on the architecture. | |
| 46 | * | |
| 47 | * @param data | |
| 48 | * The address of the data to hash. | |
| 49 | * | |
| 50 | * @param length | |
| 51 | * The length of the data to hash | |
| 52 | * | |
| 53 | * @returns | |
| 54 | * The jenkins hash for this data. | |
| 55 | */ | |
| 56 | static inline uint32_t | |
| 57 | os_hash_jenkins(const void *data, size_t length) | |
| 58 | { | |
| 59 | const uint8_t *key = (const uint8_t *)data; | |
| 60 | uint32_t hash = 0; | |
| 61 | ||
| 62 | for (size_t i = 0; i < length; i++) { | |
| 63 | hash += key[i]; | |
| 64 | hash += (hash << 10); | |
| 65 | hash ^= (hash >> 6); | |
| 66 | } | |
| 67 | ||
| 68 | hash += (hash << 3); | |
| 69 | hash ^= (hash >> 11); | |
| 70 | hash += (hash << 15); | |
| 71 | ||
| 72 | return hash; | |
| 73 | } | |
| 74 | ||
| 75 | /*! | |
| 76 | * @function os_hash_kernel_pointer | |
| 77 | * | |
| 78 | * @brief | |
| 79 | * Hashes a pointer from a zone. | |
| 80 | * | |
| 81 | * @discussion | |
| 82 | * This is a really cheap and fast hash that will behave well for pointers | |
| 83 | * allocated by the kernel. | |
| 84 | * | |
| 85 | * This should be not used for untrusted pointer values from userspace, | |
| 86 | * or cases when the pointer is somehow under the control of userspace. | |
| 87 | * | |
| 88 | * This hash function utilizes knowledge about the span of the kernel | |
| 89 | * address space and inherent alignment of zalloc/kalloc. | |
| 90 | * | |
| 91 | * @param pointer | |
| 92 | * The pointer to hash. | |
| 93 | * | |
| 94 | * @returns | |
| 95 | * The hash for this pointer. | |
| 96 | */ | |
| 97 | static inline uint32_t | |
| 98 | os_hash_kernel_pointer(const void *pointer) | |
| 99 | { | |
| 100 | uintptr_t key = (uintptr_t)pointer >> 4; | |
| 101 | key *= 0x5052acdb; | |
| 102 | return (uint32_t)key ^ __builtin_bswap32((uint32_t)key); | |
| 103 | } | |
| 104 | ||
| 105 | __END_DECLS | |
| 106 | ||
| 107 | #endif // PRIVATE | |
| 108 | #endif // _OS_HASH_H_ |