bin/varnishd/hash/hash_critbit.c
static struct objhead *
hcb_insert(const struct worker *wrk, struct hcb_root *root,
    const uint8_t *digest, struct objhead **noh)
{
	volatile uintptr_t *p;
	uintptr_t pp;
	struct hcb_y *y, *y2;
	struct objhead *oh2;
	unsigned s, s2;

	p = &root->origo;
	pp = *p;
	if (pp == 0) {
		if (noh == NULL)
			return (NULL);
		oh2 = *noh;
		*noh = NULL;
		memcpy(oh2->digest, digest, sizeof oh2->digest);
		*p = hcb_r_node(oh2);
		return (oh2);
	}

	while (hcb_is_y(pp)) {
		y = hcb_l_y(pp);
		CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
		assert(y->ptr < DIGEST_LEN);
		s = (digest[y->ptr] & y->bitmask) != 0;
		assert(s < 2);
		p = &y->leaf[s];
		pp = *p;
	}

	if (pp == 0) {
		/* We raced hcb_delete and got a NULL pointer */
		assert(noh == NULL);
		return (NULL);
	}

	assert(hcb_is_node(pp));

	/* We found a node, does it match ? */
	oh2 = hcb_l_node(pp);
	CHECK_OBJ_NOTNULL(oh2, OBJHEAD_MAGIC);
	if (!memcmp(oh2->digest, digest, DIGEST_LEN))
		return (oh2);

	if (noh == NULL)
		return (NULL);

	/* Insert */

	CAST_OBJ_NOTNULL(y2, wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
	wrk->wpriv->nhashpriv = NULL;
	(void)hcb_crit_bit(digest, oh2, y2);
	s2 = (digest[y2->ptr] & y2->bitmask) != 0;
	assert(s2 < 2);
	oh2 = *noh;
	*noh = NULL;
	memcpy(oh2->digest, digest, sizeof oh2->digest);
	y2->leaf[s2] = hcb_r_node(oh2);
	s2 = 1-s2;

	p = &root->origo;
	AN(*p);

	while (hcb_is_y(*p)) {
		y = hcb_l_y(*p);
		CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
		assert(y->critbit != y2->critbit);
		if (y->critbit > y2->critbit)
			break;
		assert(y->ptr < DIGEST_LEN);
		s = (digest[y->ptr] & y->bitmask) != 0;
		assert(s < 2);
		p = &y->leaf[s];
	}
	y2->leaf[s2] = *p;
	VWMB();
	*p = hcb_r_y(y2);
	return (oh2);
}
/*---------------------------------------------------------------------
 * Unless we have the lock, we need to be very careful about pointer
 * references into the tree, we cannot trust things to be the same
 * in two consecutive memory accesses.
 */
Unless we have the lock, we need to be very careful about pointer
references into the tree, we cannot trust things to be the same
in two consecutive memory accesses.
Unless we have the lock we need to be very careful about pointer references into the tree we cannot trust things to be the same in two consecutive memory accesses .
static struct objhead *
hcb_insert(const struct worker *wrk, struct hcb_root *root,
    const uint8_t *digest, struct objhead **noh)
{
	volatile uintptr_t *p;
	uintptr_t pp;
	struct hcb_y *y, *y2;
	struct objhead *oh2;
	unsigned s, s2;
	p = &root->origo;
	pp = *p;
	if (pp == 0) {
		if (noh == NULL)
			return (NULL);
		oh2 = *noh;
		*noh = NULL;
		memcpy(oh2->digest, digest, sizeof oh2->digest);
		*p = hcb_r_node(oh2);
		return (oh2);
	}
	while (hcb_is_y(pp)) {
		y = hcb_l_y(pp);
		CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
		assert(y->ptr < DIGEST_LEN);
		s = (digest[y->ptr] & y->bitmask) != 0;
		assert(s < 2);
		p = &y->leaf[s];
		pp = *p;
	}
	if (pp == 0) {
		assert(noh == NULL);
		return (NULL);
	}
	assert(hcb_is_node(pp));
	oh2 = hcb_l_node(pp);
	CHECK_OBJ_NOTNULL(oh2, OBJHEAD_MAGIC);
	if (!memcmp(oh2->digest, digest, DIGEST_LEN))
		return (oh2);
	if (noh == NULL)
		return (NULL);
	CAST_OBJ_NOTNULL(y2, wrk->wpriv->nhashpriv, HCB_Y_MAGIC);
	wrk->wpriv->nhashpriv = NULL;
	(void)hcb_crit_bit(digest, oh2, y2);
	s2 = (digest[y2->ptr] & y2->bitmask) != 0;
	assert(s2 < 2);
	oh2 = *noh;
	*noh = NULL;
	memcpy(oh2->digest, digest, sizeof oh2->digest);
	y2->leaf[s2] = hcb_r_node(oh2);
	s2 = 1-s2;
	p = &root->origo;
	AN(*p);
	while (hcb_is_y(*p)) {
		y = hcb_l_y(*p);
		CHECK_OBJ_NOTNULL(y, HCB_Y_MAGIC);
		assert(y->critbit != y2->critbit);
		if (y->critbit > y2->critbit)
			break;
		assert(y->ptr < DIGEST_LEN);
		s = (digest[y->ptr] & y->bitmask) != 0;
		assert(s < 2);
		p = &y->leaf[s];
	}
	y2->leaf[s2] = *p;
	VWMB();
	*p = hcb_r_y(y2);
	return (oh2);
}
static struct objhead * hcb_insert ( const struct worker * wrk , struct hcb_root * root , const uint8_t * digest , struct objhead * * noh ) { volatile uintptr_t * p ; uintptr_t pp ; struct hcb_y * y , * y2 ; struct objhead * oh2 ; unsigned s , s2 ; p = & root -> origo ; pp = * p ; if ( pp == 0 ) { if ( noh == NULL ) return ( NULL ) ; oh2 = * noh ; * noh = NULL ; memcpy ( oh2 -> digest , digest , sizeof oh2 -> digest ) ; * p = hcb_r_node ( oh2 ) ; return ( oh2 ) ; } while ( hcb_is_y ( pp ) ) { y = hcb_l_y ( pp ) ; CHECK_OBJ_NOTNULL ( y , HCB_Y_MAGIC ) ; assert ( y -> ptr < DIGEST_LEN ) ; s = ( digest [ y -> ptr ] & y -> bitmask ) != 0 ; assert ( s < 2 ) ; p = & y -> leaf [ s ] ; pp = * p ; } if ( pp == 0 ) { assert ( noh == NULL ) ; return ( NULL ) ; } assert ( hcb_is_node ( pp ) ) ; oh2 = hcb_l_node ( pp ) ; CHECK_OBJ_NOTNULL ( oh2 , OBJHEAD_MAGIC ) ; if ( ! memcmp ( oh2 -> digest , digest , DIGEST_LEN ) ) return ( oh2 ) ; if ( noh == NULL ) return ( NULL ) ; CAST_OBJ_NOTNULL ( y2 , wrk -> wpriv -> nhashpriv , HCB_Y_MAGIC ) ; wrk -> wpriv -> nhashpriv = NULL ; ( void ) hcb_crit_bit ( digest , oh2 , y2 ) ; s2 = ( digest [ y2 -> ptr ] & y2 -> bitmask ) != 0 ; assert ( s2 < 2 ) ; oh2 = * noh ; * noh = NULL ; memcpy ( oh2 -> digest , digest , sizeof oh2 -> digest ) ; y2 -> leaf [ s2 ] = hcb_r_node ( oh2 ) ; s2 = 1 - s2 ; p = & root -> origo ; AN ( * p ) ; while ( hcb_is_y ( * p ) ) { y = hcb_l_y ( * p ) ; CHECK_OBJ_NOTNULL ( y , HCB_Y_MAGIC ) ; assert ( y -> critbit != y2 -> critbit ) ; if ( y -> critbit > y2 -> critbit ) break ; assert ( y -> ptr < DIGEST_LEN ) ; s = ( digest [ y -> ptr ] & y -> bitmask ) != 0 ; assert ( s < 2 ) ; p = & y -> leaf [ s ] ; } y2 -> leaf [ s2 ] = * p ; VWMB ( ) ; * p = hcb_r_y ( y2 ) ; return ( oh2 ) ; }
Unless we have the lock, we need to be very careful about pointer
 references into the tree, we cannot trust things to be the same
 in two consecutive memory accesses.
Unless we have the lock we need to be very careful about pointer references into the tree we cannot trust things to be the same in two consecutive memory accesses .
/* We raced hcb_delete and got a NULL pointer */ /* We found a node, does it match ? */ /* Insert */