- 论坛徽章:
- 11
|
本帖最后由 zylthinking 于 2017-04-18 12:22 编辑
再更新一次? 貌似更新在这里也没什么意义, 包含一个 proc_context 的 bugfix, 另外在 linux 下增加了两个同步函数
- #ifdef __linux__
- #include <syscall.h>
- #include <unistd.h>
- static inline void lkf_node_put_wake(struct lkf_list* list, struct lkf_node* node)
- {
- node->next = NULL;
- struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
- if (ptr == &list->root.next) {
- while (-1 == syscall(__NR_futex, ptr, FUTEX_WAKE, 1, NULL, NULL, 0));
- }
- *ptr = node;
- }
- static inline struct lkf_node* lkf_node_get_wait(struct lkf_list* list)
- {
- struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
- while (ptr == NULL) {
- syscall(__NR_futex, &list->root.next, FUTEX_WAIT, NULL, NULL, NULL, 0);
- ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
- };
- struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
- *last = ptr;
- return *last;
- }
- #endif
- #if 1
- typedef struct proc_context {
- struct lkf_list list;
- int stat;
- } proc_context;
- static int proc_enter(struct proc_context* ctx, struct lkf_node* node)
- {
- lkf_node_put(&ctx->list, node);
- __sync_synchronize();
- int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
- if (n == 0) {
- return -1;
- }
- return 0;
- }
- static int proc_leave(struct proc_context* ctx)
- {
- ctx->stat = 0;
- __sync_synchronize();
- if (ctx->list.tail == &ctx->list.root.next) {
- return 0;
- }
- int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
- if (n == 0) {
- return 0;
- }
- return -1;
- }
- #endif
复制代码
更新: 增加了一个基于 lkf 的 proc_context, 使用场景: 当多个线程拿到同一个实体的数据并进行处理时, 先检查是否有其他线程已经在处理该实体数据, 若是, 将数据移交给该线程, 自身退出, 否则, 亲自处理。
还是希望看得懂的哥们仔细找找是否存在漏洞, 这玩意真是太难想了, 翻来覆去, 总是没有足够自信说没有 bug- struct proc_context {
- struct lkf_list list;
- int stat;
- };
- static int proc_enter(struct proc_context* ctx, struct lkf_node* node)
- {
- lkf_node_put(&ctx->list, node);
- int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
- if (n == 0) {
- return -1;
- }
- return 0;
- }
- static int proc_leave(struct proc_context* ctx)
- {
- ctx->stat = 0;
- if (ctx->list.tail == &ctx->list.root.next) {
- return 0;
- }
- int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
- if (n == 0) {
- return 0;
- }
- return -1;
- }
复制代码 写了一个多线程读多线程写的无锁链表, 完全是自己的思路, 但不知道之前有没有其他人已经提出来过了, 和 MS Queue 比, 应该好点吧, 自以为。
github 地址: https://github.com/zylthinking/lkf/blob/master/lkf.h, 上面有个测试程序, 已经使用 500 读线程 500 写线程 共 1亿次操作测试过了很多次, 没有出现错误。
相关帖子:http://bbs.chinaunix.net/thread-4094984-1-2.html- #ifndef lkf_h
- #define lkf_h
- struct lkf_node {
- struct lkf_node* next;
- };
- struct lkf_list {
- struct lkf_node root;
- struct lkf_node** tail;
- };
- #define LKF_INIT(name) {.root = {NULL}, .tail = &(name.root.next)}
- #define LKF_LIST(name) \
- struct lkf_list name = LKF_INIT(name)
- #define INIT_LKF(name) \
- do { \
- name->root.next = NULL; \
- name->tail = &(name->root.next); \
- } while (0)
- static inline void lkf_node_put(struct lkf_list* list, struct lkf_node* node)
- {
- struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
- *ptr = node;
- }
- static inline struct lkf_node* lkf_node_get_one(struct lkf_list* list)
- {
- struct lkf_node* head = __sync_lock_test_and_set(&(list->root.next), NULL);
- if (head == NULL) {
- return NULL;
- }
- struct lkf_node* next = head->next;
- if (next != NULL) {
- list->root.next = next;
- head->next = head;
- return head;
- }
- int b = __sync_bool_compare_and_swap(&(list->tail), &(head->next), &(list->root.next));
- if (b) {
- head->next = head;
- return head;
- }
- list->root.next = head;
- return NULL;
- }
- static inline struct lkf_node* lkf_node_get(struct lkf_list* list)
- {
- struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
- if (ptr == NULL) {
- return NULL;
- }
- struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
- *last = ptr;
- return *last;
- }
- static inline struct lkf_node* lkf_node_next(struct lkf_node* node)
- {
- struct lkf_node* ptr = node->next;
- if (ptr == NULL || ptr->next == NULL) {
- return NULL;
- }
- if (ptr == node) {
- return ptr;
- }
- node->next = ptr->next;
- ptr->next = NULL;
- return ptr;
- }
- #endif
复制代码 |
|