From 6c9c2933c2a0a55ad9907c3e0ae2ab495d8fa959 Mon Sep 17 00:00:00 2001 From: Sascha Wildner Date: Wed, 6 Jun 2012 22:11:44 +0200 Subject: [PATCH] kernel: Add . * Our DRM's drm_priv_hash.h is really what's in the other BSDs. So move it there, too. * Add a hash(9) manual page (from FreeBSD). * Adjust DRM to use our hash{init,destroy}() functions instead of rolling its own. Reported-by: ftigeot --- share/man/man9/Makefile | 7 + share/man/man9/hash.9 | 161 ++++++++++++++++++++ sys/conf/files | 1 - sys/dev/drm/drm/Makefile | 1 - sys/dev/drm/drm_hashtab.c | 14 +- sys/dev/drm/drm_subr_hash.c | 139 ----------------- sys/{dev/drm/drm_priv_hash.h => sys/hash.h} | 18 +-- 7 files changed, 176 insertions(+), 165 deletions(-) create mode 100644 share/man/man9/hash.9 delete mode 100644 sys/dev/drm/drm_subr_hash.c rename sys/{dev/drm/drm_priv_hash.h => sys/hash.h} (88%) diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile index c0f9ac8aa4..4584afb611 100644 --- a/share/man/man9/Makefile +++ b/share/man/man9/Makefile @@ -79,6 +79,7 @@ MAN= accept_filter.9 \ extattr.9 \ fetch.9 \ firmware.9 \ + hash.9 \ hashinit.9 \ hexdump.9 \ ieee80211.9 \ @@ -446,6 +447,12 @@ MLINKS+=firmware.9 firmware_get.9 \ firmware.9 firmware_put.9 \ firmware.9 firmware_register.9 \ firmware.9 firmware_unregister.9 +MLINKS+=hash.9 hash32.9 \ + hash.9 hash32_buf.9 \ + hash.9 hash32_str.9 \ + hash.9 hash32_stre.9 \ + hash.9 hash32_strn.9 \ + hash.9 hash32_strne.9 MLINKS+=hashinit.9 hashdestroy.9 \ hashinit.9 hashinit_ext.9 \ hashinit.9 phashinit.9 \ diff --git a/share/man/man9/hash.9 b/share/man/man9/hash.9 new file mode 100644 index 0000000000..c41310cafa --- /dev/null +++ b/share/man/man9/hash.9 @@ -0,0 +1,161 @@ +.\" Copyright (c) 2001 Tobias Weingartner +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.\" +.\" $OpenBSD: hash.9,v 1.5 2003/04/17 05:08:39 jmc Exp $ +.\" $FreeBSD: src/share/man/man9/hash.9,v 1.4 2007/04/09 22:55:14 thompsa Exp $ +.\" +.Dd June 6, 2012 +.Dt HASH 9 +.Os +.Sh NAME +.Nm hash , +.Nm hash32 , +.Nm hash32_buf , +.Nm hash32_str , +.Nm hash32_strn , +.Nm hash32_stre , +.Nm hash32_strne +.Nd general kernel hashing functions +.Sh SYNOPSIS +.In sys/hash.h +.Ft uint32_t +.Fn hash32_buf "const void *buf" "size_t len" "uint32_t hash" +.Ft uint32_t +.Fn hash32_str "const void *buf" "uint32_t hash" +.Ft uint32_t +.Fn hash32_strn "const void *buf" "size_t len" "uint32_t hash" +.Ft uint32_t +.Fn hash32_stre "const void *buf" "int end" "const char **ep" "uint32_t hash" +.Ft uint32_t +.Fn hash32_strne "const void *buf" "size_t len" "int end" "const char **ep" "uint32_t hash" +.Sh DESCRIPTION +The +.Fn hash32 +functions are used to give a consistent and general interface to +a decent hashing algorithm within the kernel. +These functions can be used to hash +.Tn ASCII +.Dv NUL +terminated strings, as well as blocks of memory. +.Pp +The +.Fn hash32_buf +function is used as a general buffer hashing function. +The argument +.Fa buf +is used to pass in the location, and +.Fa len +is the length of the buffer. +The argument +.Fa hash +is used to extend an existing hash, or is passed the initial value +.Dv HASHINIT +to start a new hash. +.Pp +The +.Fn hash32_str +function is used to hash a +.Dv NUL +terminated string passed in +.Fa buf +with initial hash value given in +.Fa hash . +.Pp +The +.Fn hash32_strn +function is like the +.Fn hash32_str +function, except it also takes a +.Fa len +argument, which is the maximal length of the expected string. +.Pp +The +.Fn hash32_stre +and +.Fn hash32_strne +functions are helper functions used by the kernel to hash pathname +components. +These functions have the additional termination condition +of terminating when they find a character given by +.Fa end +in the string to be hashed. +If the argument +.Fa ep +is not +.Dv NULL , +it is set to the point in the buffer at which the hash function +terminated hashing. +.Sh RETURN VALUES +The +.Fn hash32 +functions return a 32 bit hash value of the buffer or string. +.Sh EXAMPLES +.Bd -literal -offset indent +LIST_HEAD(head, cache) *hashtbl = NULL; +u_long mask = 0; + +void +sample_init(void) +{ + + hashtbl = hashinit(numwanted, type, flags, &mask); +} + +void +sample_use(char *str, int len) +{ + uint32_t hash; + + hash = hash32_str(str, HASHINIT); + hash = hash32_buf(&len, sizeof(len), hash); + hashtbl[hash & mask] = len; +} +.Ed +.Sh SEE ALSO +.Xr hashinit 9 , +.Xr kfree 9 , +.Xr kmalloc 9 +.Sh LIMITATIONS +The +.Fn hash32 +functions are only 32 bit functions. +They will prove to give poor 64 bit performance, especially for the +top 32 bits. +At the current time, this is not seen as a great limitation, as these +hash values are usually used to index into an array. +Should these hash values be used for other means, this limitation should +be revisited. +.Sh HISTORY +The +.Nm +functions were first committed to +.Nx 1.6 . +The +.Ox +versions were written and massaged for +.Ox 2.3 +by Tobias Weingartner, +and finally committed for +.Ox 3.2 . diff --git a/sys/conf/files b/sys/conf/files index d15e8d1926..54877492ab 100644 --- a/sys/conf/files +++ b/sys/conf/files @@ -1897,7 +1897,6 @@ dev/drm/drm_mm.c optional drm dev/drm/drm_pci.c optional drm dev/drm/drm_scatter.c optional drm dev/drm/drm_sman.c optional drm -dev/drm/drm_subr_hash.c optional drm dev/drm/drm_sysctl.c optional drm dev/drm/drm_vm.c optional drm dev/drm/i915/i915_dma.c optional i915drm drm diff --git a/sys/dev/drm/drm/Makefile b/sys/dev/drm/drm/Makefile index 770276157a..c9b651a760 100644 --- a/sys/dev/drm/drm/Makefile +++ b/sys/dev/drm/drm/Makefile @@ -19,7 +19,6 @@ SRCS = \ drm_pci.c \ drm_scatter.c \ drm_sman.c \ - drm_subr_hash.c \ drm_sysctl.c \ drm_vm.c diff --git a/sys/dev/drm/drm_hashtab.c b/sys/dev/drm/drm_hashtab.c index e55c76e244..08f42bdc37 100644 --- a/sys/dev/drm/drm_hashtab.c +++ b/sys/dev/drm/drm_hashtab.c @@ -24,7 +24,7 @@ * USE OR OTHER DEALINGS IN THE SOFTWARE. * * - * __FBSDID("$FreeBSD: src/sys/dev/drm/drm_hashtab.c,v 1.1 2010/01/31 14:25:29 rnoland Exp $"); + * $FreeBSD: src/sys/dev/drm/drm_hashtab.c,v 1.1 2010/01/31 14:25:29 rnoland Exp $ **************************************************************************/ /* @@ -34,21 +34,17 @@ * Thomas Hellström */ -#include "dev/drm/drmP.h" -#include "dev/drm/drm_hashtab.h" - -#if defined(__DragonFly__) -#include "dev/drm/drm_priv_hash.h" -#else #include -#endif + +#include "drmP.h" +#include "drm_hashtab.h" int drm_ht_create(struct drm_open_hash *ht, unsigned int order) { ht->size = 1 << order; ht->order = order; ht->table = NULL; - ht->table = drm_hashinit(ht->size, DRM_MEM_HASHTAB, &ht->mask); + ht->table = hashinit(ht->size, DRM_MEM_HASHTAB, &ht->mask); if (!ht->table) { DRM_ERROR("Out of memory for hash table\n"); return -ENOMEM; diff --git a/sys/dev/drm/drm_subr_hash.c b/sys/dev/drm/drm_subr_hash.c deleted file mode 100644 index aab8c11d4d..0000000000 --- a/sys/dev/drm/drm_subr_hash.c +++ /dev/null @@ -1,139 +0,0 @@ -/*- - * Copyright (c) 1982, 1986, 1991, 1993 - * The Regents of the University of California. All rights reserved. - * (c) UNIX System Laboratories, Inc. - * All or some portions of this file are derived from material licensed - * to the University of California by American Telephone and Telegraph - * Co. or Unix System Laboratories, Inc. and are reproduced herein with - * the permission of UNIX System Laboratories, Inc. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)kern_subr.c 8.3 (Berkeley) 1/21/94 - * __FBSDID("$FreeBSD: src/sys/kern/subr_hash.c,v 1.1 2010/02/21 19:53:33 ed Exp $"); - */ - -#include "dev/drm/drmP.h" -#include "dev/drm/drm_priv_hash.h" - -/* From FreeBSD's sys/systm.h */ -#ifndef HASH_NOWAIT -#define HASH_NOWAIT 0x00000001 -#endif -#ifndef HASH_WAITOK -#define HASH_WAITOK 0x00000002 -#endif - -/* - * General routine to allocate a hash table with control of memory flags. - */ -void * -drm_hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask, - int flags) -{ - long hashsize; - LIST_HEAD(generic, generic) *hashtbl; - int i; - - if (elements <= 0) - panic("hashinit: bad elements"); - - /* Exactly one of HASH_WAITOK and HASH_NOWAIT must be set. */ - KASSERT((flags & HASH_WAITOK) ^ (flags & HASH_NOWAIT), - ("Bad flags (0x%x) passed to hashinit_flags", flags)); - - for (hashsize = 1; hashsize <= elements; hashsize <<= 1) - continue; - hashsize >>= 1; - - if (flags & HASH_NOWAIT) - hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), - type, M_NOWAIT); - else - hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), - type, M_WAITOK); - - if (hashtbl != NULL) { - for (i = 0; i < hashsize; i++) - LIST_INIT(&hashtbl[i]); - *hashmask = hashsize - 1; - } - return (hashtbl); -} - -/* - * Allocate and initialize a hash table with default flag: may sleep. - */ -void * -drm_hashinit(int elements, struct malloc_type *type, u_long *hashmask) -{ - - return (drm_hashinit_flags(elements, type, hashmask, HASH_WAITOK)); -} - -void -drm_hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask) -{ - LIST_HEAD(generic, generic) *hashtbl, *hp; - - hashtbl = vhashtbl; - for (hp = hashtbl; hp <= &hashtbl[hashmask]; hp++) - if (!LIST_EMPTY(hp)) - panic("hashdestroy: hash not empty"); - free(hashtbl, type); -} - -static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, - 2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, - 6653, 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; -#define NPRIMES (sizeof(primes) / sizeof(primes[0])) - -/* - * General routine to allocate a prime number sized hash table. - */ -#if 0 -void * -drm_phashinit(int elements, struct malloc_type *type, u_long *nentries) -{ - long hashsize; - LIST_HEAD(generic, generic) *hashtbl; - int i; - - if (elements <= 0) - panic("phashinit: bad elements"); - for (i = 1, hashsize = primes[1]; hashsize <= elements;) { - i++; - if (i == NPRIMES) - break; - hashsize = primes[i]; - } - hashsize = primes[i - 1]; - hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); - for (i = 0; i < hashsize; i++) - LIST_INIT(&hashtbl[i]); - *nentries = hashsize; - return (hashtbl); -} -#endif diff --git a/sys/dev/drm/drm_priv_hash.h b/sys/sys/hash.h similarity index 88% rename from sys/dev/drm/drm_priv_hash.h rename to sys/sys/hash.h index 80f92a45de..d80fc9342d 100644 --- a/sys/dev/drm/drm_priv_hash.h +++ b/sys/sys/hash.h @@ -26,8 +26,8 @@ * $FreeBSD: src/sys/sys/hash.h,v 1.3 2007/04/09 22:55:14 thompsa Exp $ */ -#ifndef _DRM_PRIV_HASH_H -#define _DRM_PRIV_HASH_H_ +#ifndef _SYS_HASH_H +#define _SYS_HASH_H_ #include /* Convenience */ @@ -119,16 +119,4 @@ hash32_strne(const void *buf, size_t len, int end, const char **ep, return hash; } -/* Added to act as private header files for hash function */ - -void * -drm_hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask, - int flags); - -void * -drm_hashinit(int elements, struct malloc_type *type, u_long *hashmask); - -void -drm_hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask); - -#endif /* !_DRM_PRIV_HASH_H_ */ +#endif /* !_SYS_HASH_H_ */ -- 2.41.0