FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
steal_state.h
1 #ifndef __STEAL_STATE_H__
2 #define __STEAL_STATE_H__
3 
4 /*
5  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of FlashGraph.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include <atomic>
24 
25 #include "bitmap.h"
26 
27 namespace fg
28 {
29 
30 class compute_vertex;
31 
32 /*
33  * This class maintains the states to handle vertices being stolen by
34  * other threads.
35  * There are two stages:
36  * 1. normal stage: the owner thread processes messages normally.
37  * 2. stealing stage: the owner thread needs to indicate it is ready
38  * for vertices to be stolen. Whenever it processes messages to a vertex,
39  * it needs to check whether the vertex has been stolen by another thread.
40  * If it is stolen, postpone processing its messages.
41  */
42 class steal_state_t
43 {
44  // The id of the owner thread.
45  const int worker_id;
46  // Indicates the vertices stolen by other threads.
47  thread_safe_bitmap stolen_bitmap;
48 
49  // The number of vertices stolen from the owner thread.
50  std::atomic_ulong num_stolen;
51  std::atomic_ulong num_returned;
52 
53  // All threads that want to steal vertices need to increase this counter.
54  std::atomic_ulong prepare_steal;
55  // The owner thread indicates that it has entered the stealing stage and
56  // is ready for vertices to be stolen.
57  std::atomic_ulong steal_state;
58  // The owner thread indicates whether it's processing messages.
59  // If the value is odd, it is processing messages.
60  std::atomic_ulong guard;
61 
62  graph_engine &graph;
63 public:
64  steal_state_t(graph_engine &_graph, worker_thread &owner): worker_id(
65  owner.get_worker_id()), stolen_bitmap(owner.get_num_local_vertices(),
66  owner.get_node_id()), graph(_graph) {
67  num_stolen = 0;
68  num_returned = 0;
69  prepare_steal = 0;
70  steal_state = 0;
71  guard = 0;
72  }
73 
74  /*
75  * The two methods below are used by other worker threads.
76  */
77 
78  void steal_vertices(compute_vertex_pointer vertices[], int num);
79 
80  void return_vertices(vertex_id_t ids[], int num);
81 
82  bool steal_mode_enabled() const {
83  // It should be fine to use the relaxed memory order. steal_state
84  // can only be changed in the same thread.
85  return steal_state.load(std::memory_order_relaxed);
86  }
87 
88  /*
89  * The methods below are used by the owner thread.
90  */
91 
92  bool is_stolen(vertex_id_t id) const {
93  int part_id;
94  off_t off;
95  graph.get_partitioner()->map2loc(id, part_id, off);
96  return stolen_bitmap.get(off);
97  }
98 
99  bool is_stolen(local_vid_t id) const {
100  return stolen_bitmap.get(id.id);
101  }
102 
103  void guard_msg_processing() {
104  guard.fetch_add(1);
105  if (prepare_steal.load() > 0)
106  steal_state.store(1);
107  }
108 
109  void unguard_msg_processing() {
110  guard.fetch_add(1);
111  }
112 
113  void reset() {
114  assert(num_stolen == num_returned);
115  num_stolen = 0;
116  num_returned = 0;
117  prepare_steal = 0;
118  steal_state = 0;
119  guard = 0;
120  stolen_bitmap.clear();
121  }
122 
123  size_t get_num_stolen() const {
124  return num_stolen.load(std::memory_order_relaxed);
125  }
126 
127  size_t get_num_returned() const {
128  return num_returned.load(std::memory_order_relaxed);
129  }
130 };
131 
132 }
133 
134 #endif