本文介绍了jmp自编译由gcc4.4.6-3的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个C ++项目，由gcc-4.1.2-46和gcc-4.4.5-6正确编译。
但它有一个异常死循环而使用-O2编译gcc-4.4.6-3。
我使用gdb附加它，当进程运行，并找到线程正在运行，但堆栈不改变。
objdump程序，发现它有3个指令jmp自我，像这样：
432f6c：48 89 C7 MOV％RAX，％RDI
432f6f：90 NOP
432f70：E8 B3 E4 FD FF callq 411428< _Unwind_Resume @ PLT>
432f75：eb fe jmp 432f75< _ZN9oceanbase12updateserver11QueryEngine3getERKNS0_5TEKeyE + 0x4d5>
432f77：48 8D 7C 24 70 LEA 0x70（％RSP），％RDI
432f7c：48 89 C3 MOV％RAX，％RBX
432f7f：E8 9C 32 00 00 callq 436220< _ZN9oceanbase12updateserver12BitLockGuardD1Ev>
我没有在代码中使用goto。
$ b b
当代码是由gcc-4.4.6-3使用-O0编译时，
jmp自我指令消失
所以我怀疑这是gcc-4.4.6.3的错误。
代码是一个简单的多线程Hashmap，使用BitLock来保护buckets：
#define ATOMIC_CAS（val，cmpv，newv）__sync_val_compare_and_swap（（val），（cmpv），（newv））
#define ATOMIC_ADD（val，addv）__sync_add_and_fetch（（val），（addv））
#define ATOMIC_SUB（val，subv）__sync_sub_and_fetch（（val），（subv））
template< typename Key，
typename Value，
typename BucketAllocator，
typename NodeAllocator>
class LightyHashMap
{
struct Node
{
Key key;
值值;
union
{
Node * next;
int64_t flag;
};
};
static const int64_t EMPTY_FLAG = 0xffffffffffffffff;
static const int64_t INIT_UNIT_SIZE =（64L * 1024L / sizeof（Node））* sizeof（Node）;
typedef Hash< Key> HashFunc;
typedef Equal< Key> EqualFunc;
public：
LightyHashMap（BucketAllocator& bucket_allocator，NodeAllocator& node_allocator）;
〜LightyHashMap（）;
private：
DISALLOW_COPY_AND_ASSIGN（LightyHashMap）;
public：
int create（const int64_t bucket_num）;
void destroy（）;
int clear（）;
public：
inline int insert（const Key& key，const Value& value）;
inline int get（const Key& key，Value& value）;
inline int erase（const Key& key，Value * value = NULL）;
inline int64_t uninit_unit_num（）const;
inline int64_t bucket_using（）const;
inline int64_t size（）const;
private：
void init_bucket_unit_（const int64_t bucket_pos）;
private：
BucketAllocator& bucket_allocator_;
NodeAllocator& node_allocator_;
int64_t bucket_num_;
Node * buckets_;
volatile int64_t uninit_unit_num_;
uint8_t * init_units_;
BitLock bit_lock_;
int64_t bucket_using_;
int64_t size_;
HashFunc hash_func_;
EqualFunc equals_func_;
};
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
LightyHashMap<键，值，BucketAllocator，NodeAllocator> :: LightyHashMap（
BucketAllocator&放大器; bucket_allocator，
NodeAllocator&安培; node_allocator）：bucket_allocator_（bucket_allocator），
node_allocator_（node_allocator） ，
bucket_num_（0），
buckets_（NULL），
uninit_unit_num_（0），
init_units_（NULL），
bucket_using_（0），
size_（0），
hash_func_（），
equal_func_（）
{
}
模板< typename的重点，typename的价值类型名称BucketAllocator， typename NodeAllocator>
LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> ::〜LightyHashMap（）
{
destroy（）;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: create（const int64_t bucket_num）
{
int ret = common :: OB_SUCCESS;
的int64_t uninit_unit_num =（bucket_num *的sizeof（节点）/ INIT_UNIT_SIZE）\
+（（0 ==（bucket_num *的sizeof（节点）％INIT_UNIT_SIZE））？0：1）;
if（NULL！= buckets_）
{
ret = common :: OB_INIT_TWICE;
}
else if（0> = bucket_num）
{
ret = common :: OB_INVALID_ARGUMENT;
}
，否则如果（NULL ==（buckets_ =（节点*）bucket_allocator_.alloc（bucket_num *的sizeof（节点））））
{
RET =共同:: OB_MEM_OVERFLOW ;
}
，否则如果（NULL ==（init_units_ =（uint8_t有*）bucket_allocator_.alloc（uninit_unit_num *的sizeof（uint8_t有））））
{
RET =共同:: OB_MEM_OVERFLOW ;
}
else if（OB_SUCCESS！=（ret = bit_lock_.init（bucket_num）））
{
//初始化位锁失败
}
else
{
bucket_num_ = bucket_num;
uninit_unit_num_ = uninit_unit_num;
memset（init_units_，0，uninit_unit_num_ * sizeof（uint8_t））;
bucket_using_ = 0;
size_ = 0;
}
if（common :: OB_SUCCESS！= ret）
{
destroy（）;
}
return ret;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
void LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: destroy（）
{
if（NULL！= buckets_）
{
if（NULL！ init_units_）
{
for（int64_t i = 0; i {
int64_t unit_pos = i * sizeof（Node）/ INIT_UNIT_SIZE;
uint8_t ov = init_units_ [unit_pos];
if（0 ==（ov& 0x80））
{
continue;
}
Node * iter = buckets_ [i] .next;
while（EMPTY_FLAG！= buckets_ [i] .flag
&& NULL！= iter）
{
Node * tmp = iter;
iter = iter-> next;
node_allocator_.free（tmp）;
}
buckets_ [i] .flag = EMPTY_FLAG;
}
}
bucket_allocator_.free（buckets_）;
buckets_ = NULL;
}
if（NULL！= init_units_）
{
bucket_allocator_.free（init_units_）;
init_units_ = NULL;
}
bit_lock_.destroy（）;
bucket_num_ = 0;
uninit_unit_num_ = 0;
bucket_using_ = 0;
size_ = 0;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: clear（）
{
int ret = common :: OB_SUCCESS;
if（NULL == buckets_
|| NULL == init_units_）
{
ret = common :: OB_NOT_INIT;
}
else
{
for（int64_t i = 0; i {
int64_t unit_pos = i * sizeof ）/ INIT_UNIT_SIZE;
uint8_t ov = init_units_ [unit_pos];
if（0 ==（ov& 0x80））
{
continue;
}
BitLockGuard guard（bit_lock_，i）;
Node * iter = buckets_ [i] .next;
while（EMPTY_FLAG！= buckets_ [i] .flag
&& NULL！= iter）
{
Node * tmp = iter;
iter = iter-> next;
node_allocator_.free（tmp）;
}
buckets_ [i] .flag = EMPTY_FLAG;
}
uninit_unit_num_ =（bucket_num_ * sizeof（Node）/ INIT_UNIT_SIZE）\
+（（0 ==（bucket_num_ * sizeof（Node）％INIT_UNIT_SIZE））？0：1）;
memset（init_units_，0，uninit_unit_num_ * sizeof（Node））;
bucket_using_ = 0;
size_ = 0;
}
return ret;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: insert（const Key& key，const Value& value）
{
int ret = common :: OB_SUCCESS;
if（NULL == buckets_
|| NULL == init_units_）
{
ret = common :: OB_NOT_INIT;
}
else
{
int64_t hash_value = hash_func_（key）;
int64_t bucket_pos = hash_value％bucket_num_;
init_bucket_unit_（bucket_pos）;
BitLockGuard guard（bit_lock_，bucket_pos）;
if（EMPTY_FLAG == buckets_ [bucket_pos] .flag）
{
buckets_ [bucket_pos] .key = key;
buckets_ [bucket_pos] .value = value;
buckets_ [bucket_pos] .next = NULL;
common :: atomic_inc（（uint64_t *）& bucket_using_）;
common :: atomic_inc（（uint64_t *）& size_）;
}
else
{
Node * iter =&（buckets_ [bucket_pos]）;
while（true）
{
if（equal_func_（iter-> key，key））
{
ret = common :: OB_ENTRY_EXIST;
break;
}
if（NULL！= iter-> next）
{
iter = iter-> next;
}
else
{
break;
}
}
if（common :: OB_SUCCESS == ret）
{
Node * node =（Node *）node_allocator_.alloc ;
if（NULL == node）
{
ret = common :: OB_MEM_OVERFLOW;
}
else
{
node-> key = key;
node-> value = value;
node-> next = NULL;
iter-> next = node;
common :: atomic_inc（（uint64_t *）& size_）;
}
}
}
}
return ret;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: get（const Key& key，Value& value）
{
int ret = common :: OB_SUCCESS;
if（NULL == buckets_
|| NULL == init_units_）
{
ret = common :: OB_NOT_INIT;
}
else
{
int64_t hash_value = hash_func_（key）;
int64_t bucket_pos = hash_value％bucket_num_;
init_bucket_unit_（bucket_pos）;
BitLockGuard guard（bit_lock_，bucket_pos）;
ret = common :: OB_ENTRY_NOT_EXIST;
if（EMPTY_FLAG！= buckets_ [bucket_pos] .flag）
{
Node * iter =&（buckets_ [bucket_pos]）;
while（NULL！= iter）
{
if（equal_func_（iter-> key，key））
{
value = iter-> value;
ret = common :: OB_SUCCESS;
break;
}
iter = iter-> next;
}
}
}
return ret;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: erase（const Key& key，Value * value）
{
int ret = common :: OB_SUCCESS;
if（NULL == buckets_
|| NULL == init_units_）
{
ret = common :: OB_NOT_INIT;
}
else
{
int64_t hash_value = hash_func_（key）;
int64_t bucket_pos = hash_value％bucket_num_;
init_bucket_unit_（bucket_pos）;
BitLockGuard guard（bit_lock_，bucket_pos）;
ret = common :: OB_ENTRY_NOT_EXIST;
if（EMPTY_FLAG！= buckets_ [bucket_pos] .flag）
{
Node * iter =&（buckets_ [bucket_pos]）;
Node * prev = NULL;
while（NULL！= iter）
{
if（equal_func_（iter-> key，key））
{
if（NULL！= value）
{
* value = iter-> value;
}
if（NULL == prev）
{
buckets_ [bucket_pos] .flag = EMPTY_FLAG;
}
else
{
//不释放已删除的节点
prev-> next = iter-> next;
}
ret = common :: OB_SUCCESS;
break;
}
prev = iter;
iter = iter-> next;
}
}
}
return ret;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int64_t LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: uninit_unit_num（）const
{
return uninit_unit_num_;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int64_t LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: bucket_using（）const
{
return bucket_using_;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
int64_t LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: size（）const
{
return size_;
}
template< typename Key，typename Value，typename BucketAllocator，typename NodeAllocator>
void LightyHashMap< Key，Value，BucketAllocator，NodeAllocator> :: init_bucket_unit_（const int64_t bucket_pos）
{
while（0< uninit_unit_num_）
{
int64_t unit_pos = bucket_pos * sizeof（Node）/ INIT_UNIT_SIZE;
uint8_t ov = init_units_ [unit_pos];
if（ov& 0x80）
{
break;
}
ov = 0;
uint8_t nv = ov | 0x01;
if（ov == ATOMIC_CAS（&（init_units_ [unit_pos]），ov，nv））
{
int64_t ms_size = std :: min（（bucket_num_ - bucket_pos）* sizeof节点），（uint64_t）INIT_UNIT_SIZE）;
memset（（char *）buckets_ + unit_pos * INIT_UNIT_SIZE，-1，ms_size）;
ATOMIC_SUB（& uninit_unit_num_，1）;
init_units_ [unit_pos] = 0x80;
break;
}
}
}
static const uint8_t BIT_MASKS [8] = {0x01，0x02，0x04，0x08，0x10，0x20，0x40，0x80};
类BitLock
{
public：
BitLock（）：size_（0），
bits_（NULL）
{
};
〜BitLock（）
{
destroy（）
};
public：
inline int init（const int64_t size）;
inline void destroy（）;
inline int lock（const int64_t index）;
inline int unlock（const int64_t index）;
private：
int64_t size_;
uint8_t * bits_;
};
类BitLockGuard
{
public：
BitLockGuard（BitLock& lock，const int64_t index）：lock_（lock），
index_
{
lock_.lock（index_）;
};
〜BitLockGuard（）
{
lock_.unlock（index_）;
};
private：
BitLock& lock_;
const int64_t index_;
};
int BitLock :: init（const int64_t size）
{
int ret = common :: OB_SUCCESS;
if（0< size_
|| NULL！= bits_）
{
ret = common :: OB_INIT_TWICE;
}
else if（0> = size）
{
ret = common :: OB_INVALID_ARGUMENT;
}
else
{
int64_t byte_size = common :: upper_align（size，8）/ 8;
if（NULL ==（bits_ =（uint8_t *）common :: ob_malloc（byte_size）））
{
ret = common :: OB_MEM_OVERFLOW;
}
else
{
memset（bits_，0，byte_size）;
size_ = size;
}
}
return ret;
}
void BitLock :: destroy（）
{
if（NULL！= bits_）
{
common :: ob_free bits_）;
bits_ = NULL;
}
size_ = 0;
}
int BitLock :: lock（const int64_t index）
{
int ret = common :: OB_SUCCESS;
if（0> = size_
|| NULL == bits_）
{
ret = common :: OB_NOT_INIT;
}
else if（index> = size_）
{
ret = common :: OB_INVALID_ARGUMENT;
}
else
{
int64_t byte_index = index / 8;
int64_t bit_index = index％8;
while（true）
{
uint8_t ov = bits_ [byte_index];
if（ov& BIT_MASKS [bit_index]）
{
continue;
}
if（ov == ATOMIC_CAS（&（bits_ [byte_index]），ov，ov | BIT_MASKS [bit_index]））
{
break;
}
}
}
return ret;
}
int BitLock :: unlock（const int64_t index）
{
int ret = common :: OB_SUCCESS;
if（0> = size_
|| NULL == bits_）
{
ret = common :: OB_NOT_INIT;
}
else if（index> = size_）
{
ret = common :: OB_INVALID_ARGUMENT;
}
else
{
int64_t byte_index = index / 8;
int64_t bit_index = index％8;
while（true）
{
uint8_t ov = bits_ [byte_index];
if（！（ov& BIT_MASKS [bit_index]））
{
//未锁定
break;
}
if（ov == ATOMIC_CAS（&（bits_ [byte_index]），ov，ov&〜BIT_MASKS [bit_index]））
{
break;
}
}
}
return ret;
}
解决方案
我怀疑问题出在您的循环 BitLock :: lock ：
while b $ b {
uint8_t ov = bits_ [byte_index];
if（ov& BIT_MASKS [bit_index]）
{
continue;
}
if（ov == ATOMIC_CAS（&（bits_ [byte_index]），ov，ov | BIT_MASKS [bit_index]））
{
break;
}
}
__ sync_val_compare_and_swap 在你的宏中将作为内存屏障，防止编译器/处理器推测它的负载，但它不会做任何关于负载之前，所以条件 ov&可以在 __ sync_val_compare_and_swap bits_ [byte_index] 的值优化BIT_MASKS [bit_index]
请尝试以下代码： while（true）
{
uint8_t ov = bits_ [byte_index];
if（ov& BIT_MASKS [bit_index]）
{
__sync_synchronize（）; //或定义ATOMIC_SYNC如果你喜欢
continue;
}
if（ov == ATOMIC_CAS（&（bits_ [byte_index]），ov，ov | BIT_MASKS [bit_index]））
{
break;
}
}
__ sync_synchronize 内存屏障将防止循环退化为一个简单的。
I have a C++ project, run rightly compiled by gcc-4.1.2-46 and gcc-4.4.5-6
But it has an abnormal dead loop while compiled by gcc-4.4.6-3 using -O2.
I use gdb to attach it when the process running, and find the thread is running but the stack does not change.
objdump the program, find that it has 3 instruction jmp to self, like this:
432f6c: 48 89 c7 mov %rax,%rdi
432f6f: 90 nop
432f70: e8 b3 e4 fd ff callq 411428 <_Unwind_Resume@plt>
432f75: eb fe jmp 432f75 <_ZN9oceanbase12updateserver11QueryEngine3getERKNS0_5TEKeyE+0x4d5>
432f77: 48 8d 7c 24 70 lea 0x70(%rsp),%rdi
432f7c: 48 89 c3 mov %rax,%rbx
432f7f: e8 9c 32 00 00 callq 436220 <_ZN9oceanbase12updateserver12BitLockGuardD1Ev>
I have not used "goto" in code.
When the code is compiled by gcc-4.4.6-3 using -O0,
the jmp to self instruction disappeared
So I doubt it is a bug of gcc-4.4.6.3.
The code is a simple multi-thread Hashmap using BitLock to protect the buckets:
#define ATOMIC_CAS(val, cmpv, newv) __sync_val_compare_and_swap((val), (cmpv), (newv))
#define ATOMIC_ADD(val, addv) __sync_add_and_fetch((val), (addv))
#define ATOMIC_SUB(val, subv) __sync_sub_and_fetch((val), (subv))
template <typename Key,
typename Value,
typename BucketAllocator,
typename NodeAllocator>
class LightyHashMap
{
struct Node
{
Key key;
Value value;
union
{
Node *next;
int64_t flag;
};
};
static const int64_t EMPTY_FLAG = 0xffffffffffffffff;
static const int64_t INIT_UNIT_SIZE = (64L * 1024L / sizeof(Node)) * sizeof(Node);
typedef Hash<Key> HashFunc;
typedef Equal<Key> EqualFunc;
public:
LightyHashMap(BucketAllocator &bucket_allocator, NodeAllocator &node_allocator);
~LightyHashMap();
private:
DISALLOW_COPY_AND_ASSIGN(LightyHashMap);
public:
int create(const int64_t bucket_num);
void destroy();
int clear();
public:
inline int insert(const Key &key, const Value &value);
inline int get(const Key &key, Value &value);
inline int erase(const Key &key, Value *value = NULL);
inline int64_t uninit_unit_num() const;
inline int64_t bucket_using() const;
inline int64_t size() const;
private:
void init_bucket_unit_(const int64_t bucket_pos);
private:
BucketAllocator &bucket_allocator_;
NodeAllocator &node_allocator_;
int64_t bucket_num_;
Node *buckets_;
volatile int64_t uninit_unit_num_;
uint8_t *init_units_;
BitLock bit_lock_;
int64_t bucket_using_;
int64_t size_;
HashFunc hash_func_;
EqualFunc equal_func_;
};
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::LightyHashMap(
BucketAllocator &bucket_allocator,
NodeAllocator &node_allocator) : bucket_allocator_(bucket_allocator),
node_allocator_(node_allocator),
bucket_num_(0),
buckets_(NULL),
uninit_unit_num_(0),
init_units_(NULL),
bucket_using_(0),
size_(0),
hash_func_(),
equal_func_()
{
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::~LightyHashMap()
{
destroy();
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::create(const int64_t bucket_num)
{
int ret = common::OB_SUCCESS;
int64_t uninit_unit_num = (bucket_num * sizeof(Node) / INIT_UNIT_SIZE) \
+ ((0 == (bucket_num * sizeof(Node) % INIT_UNIT_SIZE)) ? 0 : 1);
if (NULL != buckets_)
{
ret = common::OB_INIT_TWICE;
}
else if (0 >= bucket_num)
{
ret = common::OB_INVALID_ARGUMENT;
}
else if (NULL == (buckets_ = (Node*)bucket_allocator_.alloc(bucket_num * sizeof(Node))))
{
ret = common::OB_MEM_OVERFLOW;
}
else if (NULL == (init_units_ = (uint8_t*)bucket_allocator_.alloc(uninit_unit_num * sizeof(uint8_t))))
{
ret = common::OB_MEM_OVERFLOW;
}
else if (OB_SUCCESS != (ret = bit_lock_.init(bucket_num)))
{
// init bit lock fail
}
else
{
bucket_num_ = bucket_num;
uninit_unit_num_ = uninit_unit_num;
memset(init_units_, 0, uninit_unit_num_ * sizeof(uint8_t));
bucket_using_ = 0;
size_ = 0;
}
if (common::OB_SUCCESS != ret)
{
destroy();
}
return ret;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
void LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::destroy()
{
if (NULL != buckets_)
{
if (NULL != init_units_)
{
for (int64_t i = 0; i < bucket_num_; i++)
{
int64_t unit_pos = i * sizeof(Node) / INIT_UNIT_SIZE;
uint8_t ov = init_units_[unit_pos];
if (0 == (ov & 0x80))
{
continue;
}
Node *iter = buckets_[i].next;
while (EMPTY_FLAG != buckets_[i].flag
&& NULL != iter)
{
Node *tmp = iter;
iter = iter->next;
node_allocator_.free(tmp);
}
buckets_[i].flag = EMPTY_FLAG;
}
}
bucket_allocator_.free(buckets_);
buckets_ = NULL;
}
if (NULL != init_units_)
{
bucket_allocator_.free(init_units_);
init_units_ = NULL;
}
bit_lock_.destroy();
bucket_num_ = 0;
uninit_unit_num_ = 0;
bucket_using_ = 0;
size_ = 0;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::clear()
{
int ret = common::OB_SUCCESS;
if (NULL == buckets_
|| NULL == init_units_)
{
ret = common::OB_NOT_INIT;
}
else
{
for (int64_t i = 0; i < bucket_num_; i++)
{
int64_t unit_pos = i * sizeof(Node) / INIT_UNIT_SIZE;
uint8_t ov = init_units_[unit_pos];
if (0 == (ov & 0x80))
{
continue;
}
BitLockGuard guard(bit_lock_, i);
Node *iter = buckets_[i].next;
while (EMPTY_FLAG != buckets_[i].flag
&& NULL != iter)
{
Node *tmp = iter;
iter = iter->next;
node_allocator_.free(tmp);
}
buckets_[i].flag = EMPTY_FLAG;
}
uninit_unit_num_ = (bucket_num_ * sizeof(Node) / INIT_UNIT_SIZE) \
+ ((0 == (bucket_num_ * sizeof(Node) % INIT_UNIT_SIZE)) ? 0 : 1);
memset(init_units_, 0, uninit_unit_num_ * sizeof(Node));
bucket_using_ = 0;
size_ = 0;
}
return ret;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::insert(const Key &key, const Value &value)
{
int ret = common::OB_SUCCESS;
if (NULL == buckets_
|| NULL == init_units_)
{
ret = common::OB_NOT_INIT;
}
else
{
int64_t hash_value = hash_func_(key);
int64_t bucket_pos = hash_value % bucket_num_;
init_bucket_unit_(bucket_pos);
BitLockGuard guard(bit_lock_, bucket_pos);
if (EMPTY_FLAG == buckets_[bucket_pos].flag)
{
buckets_[bucket_pos].key = key;
buckets_[bucket_pos].value = value;
buckets_[bucket_pos].next = NULL;
common::atomic_inc((uint64_t*)&bucket_using_);
common::atomic_inc((uint64_t*)&size_);
}
else
{
Node *iter = &(buckets_[bucket_pos]);
while (true)
{
if (equal_func_(iter->key, key))
{
ret = common::OB_ENTRY_EXIST;
break;
}
if (NULL != iter->next)
{
iter = iter->next;
}
else
{
break;
}
}
if (common::OB_SUCCESS == ret)
{
Node *node = (Node*)node_allocator_.alloc(sizeof(Node));
if(NULL == node)
{
ret = common::OB_MEM_OVERFLOW;
}
else
{
node->key = key;
node->value = value;
node->next = NULL;
iter->next = node;
common::atomic_inc((uint64_t*)&size_);
}
}
}
}
return ret;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::get(const Key &key, Value &value)
{
int ret = common::OB_SUCCESS;
if (NULL == buckets_
|| NULL == init_units_)
{
ret = common::OB_NOT_INIT;
}
else
{
int64_t hash_value = hash_func_(key);
int64_t bucket_pos = hash_value % bucket_num_;
init_bucket_unit_(bucket_pos);
BitLockGuard guard(bit_lock_, bucket_pos);
ret = common::OB_ENTRY_NOT_EXIST;
if (EMPTY_FLAG != buckets_[bucket_pos].flag)
{
Node *iter = &(buckets_[bucket_pos]);
while (NULL != iter)
{
if (equal_func_(iter->key, key))
{
value = iter->value;
ret = common::OB_SUCCESS;
break;
}
iter = iter->next;
}
}
}
return ret;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::erase(const Key &key, Value *value)
{
int ret = common::OB_SUCCESS;
if (NULL == buckets_
|| NULL == init_units_)
{
ret = common::OB_NOT_INIT;
}
else
{
int64_t hash_value = hash_func_(key);
int64_t bucket_pos = hash_value % bucket_num_;
init_bucket_unit_(bucket_pos);
BitLockGuard guard(bit_lock_, bucket_pos);
ret = common::OB_ENTRY_NOT_EXIST;
if (EMPTY_FLAG != buckets_[bucket_pos].flag)
{
Node *iter = &(buckets_[bucket_pos]);
Node *prev = NULL;
while (NULL != iter)
{
if (equal_func_(iter->key, key))
{
if (NULL != value)
{
*value = iter->value;
}
if (NULL == prev)
{
buckets_[bucket_pos].flag = EMPTY_FLAG;
}
else
{
// do not free deleted node
prev->next = iter->next;
}
ret = common::OB_SUCCESS;
break;
}
prev = iter;
iter = iter->next;
}
}
}
return ret;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int64_t LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::uninit_unit_num() const
{
return uninit_unit_num_;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int64_t LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::bucket_using() const
{
return bucket_using_;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
int64_t LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::size() const
{
return size_;
}
template <typename Key, typename Value, typename BucketAllocator, typename NodeAllocator>
void LightyHashMap<Key, Value, BucketAllocator, NodeAllocator>::init_bucket_unit_(const int64_t bucket_pos)
{
while (0 < uninit_unit_num_)
{
int64_t unit_pos = bucket_pos * sizeof(Node) / INIT_UNIT_SIZE;
uint8_t ov = init_units_[unit_pos];
if (ov & 0x80)
{
break;
}
ov = 0;
uint8_t nv = ov | 0x01;
if (ov == ATOMIC_CAS(&(init_units_[unit_pos]), ov, nv))
{
int64_t ms_size = std::min((bucket_num_ - bucket_pos) * sizeof(Node), (uint64_t)INIT_UNIT_SIZE);
memset((char*)buckets_ + unit_pos * INIT_UNIT_SIZE, -1, ms_size);
ATOMIC_SUB(&uninit_unit_num_, 1);
init_units_[unit_pos] = 0x80;
break;
}
}
}
//////////////////////////////////////////////////////////////////////////////////////////
static const uint8_t BIT_MASKS[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
class BitLock
{
public:
BitLock() : size_(0),
bits_(NULL)
{
};
~BitLock()
{
destroy();
};
public:
inline int init(const int64_t size);
inline void destroy();
inline int lock(const int64_t index);
inline int unlock(const int64_t index);
private:
int64_t size_;
uint8_t *bits_;
};
class BitLockGuard
{
public:
BitLockGuard(BitLock &lock, const int64_t index) : lock_(lock),
index_(index)
{
lock_.lock(index_);
};
~BitLockGuard()
{
lock_.unlock(index_);
};
private:
BitLock &lock_;
const int64_t index_;
};
int BitLock::init(const int64_t size)
{
int ret = common::OB_SUCCESS;
if (0 < size_
|| NULL != bits_)
{
ret = common::OB_INIT_TWICE;
}
else if (0 >= size)
{
ret = common::OB_INVALID_ARGUMENT;
}
else
{
int64_t byte_size = common::upper_align(size, 8) / 8;
if (NULL == (bits_ = (uint8_t*)common::ob_malloc(byte_size)))
{
ret = common::OB_MEM_OVERFLOW;
}
else
{
memset(bits_, 0, byte_size);
size_ = size;
}
}
return ret;
}
void BitLock::destroy()
{
if (NULL != bits_)
{
common::ob_free(bits_);
bits_ = NULL;
}
size_ = 0;
}
int BitLock::lock(const int64_t index)
{
int ret = common::OB_SUCCESS;
if (0 >= size_
|| NULL == bits_)
{
ret = common::OB_NOT_INIT;
}
else if (index >= size_)
{
ret = common::OB_INVALID_ARGUMENT;
}
else
{
int64_t byte_index = index / 8;
int64_t bit_index = index % 8;
while (true)
{
uint8_t ov = bits_[byte_index];
if (ov & BIT_MASKS[bit_index])
{
continue;
}
if (ov == ATOMIC_CAS(&(bits_[byte_index]), ov, ov | BIT_MASKS[bit_index]))
{
break;
}
}
}
return ret;
}
int BitLock::unlock(const int64_t index)
{
int ret = common::OB_SUCCESS;
if (0 >= size_
|| NULL == bits_)
{
ret = common::OB_NOT_INIT;
}
else if (index >= size_)
{
ret = common::OB_INVALID_ARGUMENT;
}
else
{
int64_t byte_index = index / 8;
int64_t bit_index = index % 8;
while (true)
{
uint8_t ov = bits_[byte_index];
if (!(ov & BIT_MASKS[bit_index]))
{
// have not locked
break;
}
if (ov == ATOMIC_CAS(&(bits_[byte_index]), ov, ov & ~BIT_MASKS[bit_index]))
{
break;
}
}
}
return ret;
}
解决方案
I suspect the problem is in your loop in BitLock::lock:
while (true)
{
uint8_t ov = bits_[byte_index];
if (ov & BIT_MASKS[bit_index])
{
continue;
}
if (ov == ATOMIC_CAS(&(bits_[byte_index]), ov, ov | BIT_MASKS[bit_index]))
{
break;
}
}
The __sync_val_compare_and_swap in your ATOMIC_CAS macro will act as memory barrier, preventing the compiler/processor from speculating loads across it, but it won't do anything about loads before it, so the condition ov & BIT_MASKS[bit_index] could be optimized based on the value of bits_[byte_index] before the __sync_val_compare_and_swap call and thus resulting in an infinite loop.
Try the following, instead:
while (true)
{
uint8_t ov = bits_[byte_index];
if (ov & BIT_MASKS[bit_index])
{
__sync_synchronize(); // or define ATOMIC_SYNC if you prefer
continue;
}
if (ov == ATOMIC_CAS(&(bits_[byte_index]), ov, ov | BIT_MASKS[bit_index]))
{
break;
}
}
The __sync_synchronize memory barrier will prevent the loop from degenerating into a trivial one.
这篇关于jmp自编译由gcc4.4.6-3的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！