[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v3 08/11] qht: QEMU's fast, resizable and scalab
From: |
Emilio G. Cota |
Subject: |
Re: [Qemu-devel] [PATCH v3 08/11] qht: QEMU's fast, resizable and scalable Hash Table |
Date: |
Sun, 24 Apr 2016 17:58:43 -0400 |
User-agent: |
Mutt/1.5.23 (2014-03-12) |
On Sun, Apr 24, 2016 at 13:01:31 -0700, Richard Henderson wrote:
> On 04/19/2016 04:07 PM, Emilio G. Cota wrote:
> >+static void qht_insert__locked(struct qht *ht, struct qht_map *map,
> >+ struct qht_bucket *head, void *p, uint32_t
> >hash)
> >+{
> >+ struct qht_bucket *b = head;
> >+ struct qht_bucket *prev = NULL;
> >+ struct qht_bucket *new = NULL;
> >+ int i;
> >+
> >+ for (;;) {
> >+ if (b == NULL) {
> >+ b = qemu_memalign(QHT_BUCKET_ALIGN, sizeof(*b));
> >+ memset(b, 0, sizeof(*b));
> >+ new = b;
> >+ }
> >+ for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
> >+ if (b->hashes[i]) {
> >+ continue;
> >+ }
>
> Surely that's b->pointers[i] != NULL. We've made no provision that the hash
> function must return non-zero.
Good catch! I initially banned 0 from being a valid hash value,
knowing that I'd have to eventually test how stupid this assumption
was, but I forgot to do so.
It turns out that banning any hash value is a stupid idea.
For example, looping over [0,0xffffffff] shows that
xxh32(0x7aac3812, seed=1) == 0.
Will fix this in v4 -- the only assumption will be that the passed
pointer should be !NULL.
> >+static inline bool qht_remove__locked(struct qht_map *map, struct
> >qht_bucket *b,
> >+ const void *p, uint32_t hash)
> >+{
> >+ int i;
> >+
> >+ do {
> >+ for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
> >+ if (b->hashes[i] == hash && b->pointers[i] == p) {
>
> Don't you only need to test p here?
Fair point. Will fix in v4.
Thanks,
Emilio
- Re: [Qemu-devel] [PATCH v3 04/11] include/processor.h: define cpu_relax(), (continued)
- [Qemu-devel] [PATCH v3 03/11] seqlock: rename write_lock/unlock to write_begin/end, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 10/11] tb hash: track translated blocks with qht, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 07/11] tb hash: hash phys_pc, pc, and flags with xxhash, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 09/11] qht: add test program, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 08/11] qht: QEMU's fast, resizable and scalable Hash Table, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 06/11] exec: add tb_hash_func5, derived from xxhash, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 11/11] translate-all: add tb hash bucket info to 'info jit' dump, Emilio G. Cota, 2016/04/19