Author: Armin Rigo <[email protected]>
Branch: bag
Changeset: r1574:cfd89ce23688
Date: 2015-01-23 22:05 +0100
http://bitbucket.org/pypy/stmgc/changeset/cfd89ce23688/
Log: getting started
diff --git a/c7/stm/bag.c b/c7/stm/bag.c
new file mode 100644
--- /dev/null
+++ b/c7/stm/bag.c
@@ -0,0 +1,85 @@
+/*
+Design of stmgc's "bag" objects
+===============================
+
+A "bag" is an unordered list of objects. You can only add objects and
+pop a random object.
+
+Conflicts never occur, but popping may return "the bag looks empty",
+which can be wrong in the serialized order. The caller should be
+ready to handle this case. The guarantee is that if you get the
+result "the bag looks empty" in all threads that may add objects to
+it, and afterwards none of the threads adds any object, then at this
+point the bag is really empty.
+
+
+Implementation
+--------------
+
+In raw memory, for each segment, we have a list and a deque:
+
+ abort list deque
+ +--------------+ +-----------------------+---------------+
+ | already | | next items | added in this |
+ | popped items | | to pop | transaction |
+ +--------------+ +-----------------------+---------------+
+
+Adding objects puts them at the right end of the deque. Popping them
+takes them off the left end and stores a copy of the pointer into a
+separate list. This list, the "abort list", is only used to re-add
+the objects in case the transaction aborts.
+
+If, when we try to pop, we find that the deque is completely empty,
+then we try to "steal" some items from another segment's deque. This
+movement is done completely outside the normal STM rules: the objects
+remain moved even after an abort. More precisely, we take some
+objects from the left end of the other segment's deque (but not from
+the "added in this transaction" part) and add them to our own deque.
+Our own "added in this transaction" part remains empty, and the
+objects are not copied in the other transaction's abort list. This
+is done with careful compare-and-swaps.
+*/
+
+
+struct stm_bag_seg_s {
+ struct deque_block_s *deque_left, *deque_middle, *deque_right;
+ deque_idx_t deque_left_pos, deque_middle_pos, deque_right_pos;
+ struct list_s *abort_list;
+};
+
+struct stm_bag_s {
+ struct stm_bag_seg_s by_segment[STM_NB_SEGMENTS];
+};
+
+stm_bag_t *stm_bag_create(void)
+{
+ int i;
+ stm_bag_t *bag = malloc(sizeof(stm_bag_t));
+ assert(bag);
+ for (i = 0; i < STM_NB_SEGMENTS; i++) {
+ struct stm_bag_seg_s *bs = &bag->by_segment[i];
+ struct deque_block_s *block = deque_new_block();
+ bs->deque_left = block;
+ bs->deque_middle = block;
+ bs->deque_right = block;
+ bs->deque_left_pos = 0;
+ bs->deque_middle_pos = 0;
+ bs->deque_right_pos = 0;
+ LIST_CREATE(bs->abort_list);
+ }
+ return bag;
+}
+
+void stm_bag_free(stm_bag_t *bag)
+{
+ int i;
+ for (i = 0; i < STM_NB_SEGMENTS; i++) {
+ struct stm_bag_seg_s *bs = &bag->by_segment[i];
+ while (bs->deque_left) {
+ struct deque_block_s *block = bs->deque_left;
+ bs->deque_left = block->next;
+ deque_free_block(block);
+ }
+ LIST_FREE(bs->abort_list);
+ }
+}
diff --git a/c7/stm/list.h b/c7/stm/list.h
--- a/c7/stm/list.h
+++ b/c7/stm/list.h
@@ -218,3 +218,27 @@
TREE_FIND(*tree, addr, result, return false);
return true;
}
+
+/************************************************************/
+
+#define DEQUE_BLOCK_SIZE 31
+typedef unsigned char deque_idx_t;
+
+struct deque_block_s {
+ struct deque_block_s *next;
+ uintptr_t items[DEQUE_BLOCK_SIZE];
+};
+
+static inline struct deque_block_s *deque_new_block(void)
+{
+ struct deque_block_s *db = malloc(sizeof(struct deque_block_s));
+ if (db == NULL)
+ stm_fatalerror("out of memory in deque_new_block"); /* XXX */
+ db->next = NULL;
+ return db;
+}
+
+static inline void deque_free_block(struct deque_block_s *db)
+{
+ free(db);
+}
diff --git a/c7/stmgc.h b/c7/stmgc.h
--- a/c7/stmgc.h
+++ b/c7/stmgc.h
@@ -553,6 +553,13 @@
object_t *object;
};
+/* Bags, i.e. unordered lists. */
+typedef struct stm_bag_s stm_bag_t;
+stm_bag_t *stm_bag_create(void);
+void stm_bag_free(stm_bag_t *);
+void stm_bag_add(stm_bag_t *, object_t *);
+object_t *stm_bag_try_pop(stm_bag_t *);
+
/* ==================== END ==================== */
#endif
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
