src/server/tree_physics.c

   1 #include <assert.h>
   2 #include <dragonstd/array.h>
   3 #include <dragonstd/list.h>
   4 #include <dragonstd/tree.h>
   5 #include <errno.h>
   6 #include <stdbool.h>
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <time.h>
  10 #include "common/facedir.h"
  11 #include "server/server_node.h"
  12 #include "server/server_terrain.h"
  13 #include "server/tree_physics.h"
  14 #include "server/voxel_depth_search.h"
  15
  16 typedef struct {
  17         v3s32 root;
  18         bool deadlock;
  19         Tree chunks;
  20 } CheckTreeArg;
  21
  22 typedef struct {
  23         TerrainChunk *chunk;
  24         TerrainNode *node;
  25         u32 *tgs;
  26 } CheckTreeSearchNodeMeta;
  27
  28 static inline bool is_tree_with_root(TerrainNode *node)
  29 {
  30         switch (node->type) {
  31                 NODES_TREE
  32                         return ((TreeData *) node->data)->has_root;
  33
  34                 default:
  35                         return false;
  36         }
  37 }
  38
  39 static int cmp_chunk(const TerrainChunk *chunk, const v3s32 *pos)
  40 {
  41         return v3s32_cmp(&chunk->pos, pos);
  42 }
  43
  44 static void unlock_chunk(TerrainChunk *chunk)
  45 {
  46         pthread_rwlock_unlock(&chunk->lock);
  47 }
  48
  49 static void init_search_node(DepthSearchNode *search_node, CheckTreeArg *arg)
  50 {
  51         // first, get chunk position and offset
  52         v3s32 chunkp = terrain_chunkp(search_node->pos);
  53
  54         // check for chunk in cache
  55         TerrainChunk *chunk = tree_get(&arg->chunks, &chunkp, &cmp_chunk, NULL);
  56
  57         // if not found in cache, get it from server_terrain and lock it
  58         if (!chunk) {
  59                 chunk = terrain_get_chunk(server_terrain, chunkp, CHUNK_MODE_PASSIVE);
  60
  61                 // check if chunk is unloaded
  62                 if (!chunk) {
  63                         // if chunk is unloaded, don't remove the tree, it might have a connection to ground
  64                         search_node->type = DEPTH_SEARCH_TARGET;
  65
  66                         // done
  67                         return;
  68                 }
  69
  70                 // try to obtain the chunk lock
  71                 int lock_err = pthread_rwlock_wrlock(&chunk->lock);
  72
  73                 // a deadlock might occur because of the order the chunks are locked
  74                 if (lock_err == EDEADLK) {
  75                         // notify caller deadlock has occured
  76                         arg->deadlock = true;
  77
  78                         // finish search directly
  79                         search_node->type = DEPTH_SEARCH_TARGET;
  80
  81                         // done
  82                         return;
  83                 }
  84
  85                 // assert that no different error has occured while trying to obtain the lock
  86                 assert(lock_err == 0);
  87
  88                 // insert chunk into cache
  89                 tree_add(&arg->chunks, &chunk->pos, chunk, &cmp_chunk, NULL);
  90         }
  91
  92         // get node offset
  93         v3s32 offset = terrain_offset(search_node->pos);
  94
  95         // type coersion for easier access
  96         TerrainChunkMeta *meta = chunk->extra;
  97
  98         // pointer to node and generation stage
  99         TerrainNode *node = &chunk->data[offset.x][offset.y][offset.z];
 100         u32 *tgs = &meta->tgsb.raw.nodes[offset.x][offset.y][offset.z];
 101
 102         // type coersion for easier access
 103         TreeData *data = node->data;
 104
 105         // have we found terrain?
 106         if (*tgs == STAGE_TERRAIN && node->type != NODE_AIR) {
 107                 // if we've reached the target, set search node type accordingly
 108                 search_node->type = DEPTH_SEARCH_TARGET;
 109         } else if (is_tree_with_root(node) && v3s32_equals(arg->root, data->root)) {
 110                 // if node is part of our tree, continue search
 111                 search_node->type = DEPTH_SEARCH_PATH;
 112
 113                 // allocate meta storage
 114                 CheckTreeSearchNodeMeta *search_meta = search_node->extra = malloc(sizeof *search_meta);
 115
 116                 // store chunk, node and stage pointer for later
 117                 search_meta->chunk = chunk;
 118                 search_meta->node = node;
 119                 search_meta->tgs = tgs;
 120         } else {
 121                 // otherwise, this is a roadblock
 122                 search_node->type = DEPTH_SEARCH_BLOCK;
 123         }
 124 }
 125
 126 static void free_search_node(DepthSearchNode *node)
 127 {
 128         if (node->extra)
 129                 free(node->extra);
 130
 131         free(node);
 132 }
 133
 134 static void destroy_search_node(DepthSearchNode *node, List *changed_chunks)
 135 {
 136         if (node->type == DEPTH_SEARCH_PATH && !(*node->success)) {
 137                 // this is a tree/leaves node without connection to ground
 138
 139                 CheckTreeSearchNodeMeta *meta = node->extra;
 140
 141                 // overwrite node and generation stage
 142                 *meta->node = server_node_create(NODE_AIR);
 143                 *meta->tgs  = STAGE_PLAYER;
 144
 145                 // flag chunk as changed
 146                 list_add(changed_chunks, meta->chunk, meta->chunk, &cmp_ref, NULL);
 147         }
 148
 149         free_search_node(node);
 150 }
 151
 152 /*
 153         Check whether all positions (that are part of the same tree) still are connected to the ground.
 154         Destroy any tree parts without ground connection.
 155
 156         The advantage of grouping them together is that they can use the same search cache.
 157 */
 158 static bool check_tree(v3s32 root, Array *positions, Array *chunks)
 159 {
 160         CheckTreeArg arg;
 161         // inform depth search callbacks about root of tree (to only match nodes that belong to it)
 162         arg.root = root;
 163         // output parameter to prevent deadlocks
 164         arg.deadlock = false;
 165         // cache chunks, to accelerate lookup and prevent locking them twice
 166         tree_ini(&arg.chunks);
 167
 168         // add the chunks the starting points are in to the chunk cache
 169         for (size_t i = 0; i < chunks->siz; i++) {
 170                 TerrainChunk *chunk = ((TerrainChunk **) chunks->ptr)[i];
 171                 tree_add(&arg.chunks, &chunk->pos, chunk, &cmp_chunk, NULL);
 172         }
 173
 174         // nodes that have been visited
 175         // serves as search cache and contains all tree nodes, to remove them if no ground found
 176         Tree visit;
 177         tree_ini(&visit);
 178
 179         // success means ground has been found
 180
 181         // true if ground has been found for all positions
 182         bool success_all = true;
 183         // individual buffer for each start position (required by depth search algo)
 184         bool success_buf[positions->siz];
 185
 186         // iterate over start positions
 187         for (size_t i = 0; i < positions->siz; i++) {
 188                 success_buf[i] = false;
 189
 190                 // call depth search algorithm to collect positions and find ground
 191                 if (!voxel_depth_search(((v3s32 *) positions->ptr)[i], (void *) &init_search_node, &arg,
 192                                 &success_buf[i], &visit))
 193                         success_all = false;
 194
 195                 // immediately stop if there was a deadlock
 196                 if (arg.deadlock)
 197                         break;
 198         }
 199
 200         if (success_all || arg.deadlock) {
 201                 // ground has been found for all parts (or a deadlock was detected)
 202
 203                 // if ground has been found for all, there is no need to pass more complex callback
 204                 tree_clr(&visit, &free_search_node, NULL, NULL, 0);
 205
 206                 // unlock grabbed chunks
 207                 tree_clr(&arg.chunks, &unlock_chunk, NULL, NULL, 0);
 208
 209                 // return false if there was a deadlock - caller will reinitiate search
 210                 return !arg.deadlock;
 211         }
 212
 213         // keep track of changed chunks
 214         List changed_chunks;
 215         list_ini(&changed_chunks);
 216
 217         // some or all positions have no connection to ground, pass callback to destroy nodes without
 218         tree_clr(&visit, &destroy_search_node, &changed_chunks, NULL, 0);
 219
 220         // now, unlock all the chunks (before sending some of them)
 221         tree_clr(&arg.chunks, &unlock_chunk, NULL, NULL, 0);
 222
 223         // send changed chunks
 224         server_terrain_lock_and_send_chunks(&changed_chunks);
 225
 226         // done
 227         return true;
 228 }
 229
 230 /*
 231         To be called after a node has been removed.
 232         For all neigbors that are part of a tree, check whether the tree now still has connection to
 233                 the ground, destroy tree (partly) otherwise.
 234
 235         - select neighbor nodes that are leaves or wood
 236         - in every iteration, select only the nodes that belong to the same tree (have the same root)
 237         - in every iteration, keep the chunks the selected nodes belong to locked
 238         - skip nodes that don't match the currently selected root, process them in a later iteration
 239 */
 240 void tree_physics_check(v3s32 center)
 241 {
 242         // remember directions that have been processed
 243         bool dirs[6] = {false};
 244
 245         bool skipped;
 246         do {
 247                 skipped = false;
 248
 249                 // the first node that has a root will initialize these variables
 250                 bool selected_root = false;
 251                 v3s32 root;
 252
 253                 // remember selected positions and their associated locked chunks
 254                 Array positions, chunks;
 255                 array_ini(&positions, sizeof(v3s32), 5);
 256                 array_ini(&chunks, sizeof(TerrainChunk *), 5);
 257
 258                 // remember indices of positions selected in this iteration
 259                 bool selected[6] = {false};
 260
 261                 for (int i = 0; i < 6; i++) {
 262                         // we already processed this direction
 263                         if (dirs[i])
 264                                 continue;
 265
 266                         // this may change back to false if we skip
 267                         dirs[i] = true;
 268
 269                         // facedir contains offsets to neighbor nodes
 270                         v3s32 pos = v3s32_add(center, facedir[i]);
 271
 272                         // get chunk
 273                         v3s32 offset;
 274                         TerrainChunk *chunk = terrain_get_chunk_nodep(server_terrain, pos, &offset, CHUNK_MODE_PASSIVE);
 275                         if (!chunk)
 276                                 continue;
 277
 278                         // check if chunk is already locked
 279                         bool locked_before = array_idx(&chunks, &chunk) != -1;
 280
 281                         // lock if not locked
 282                         // fixme: a deadlock can happen here lol
 283                         if (!locked_before)
 284                                 assert(pthread_rwlock_wrlock(&chunk->lock) == 0);
 285
 286                         // now that chunk is locked, actually get node
 287                         TerrainNode *node = &chunk->data[offset.x][offset.y][offset.z];
 288
 289                         // check whether we're dealing with a tree node that has a root
 290                         if (is_tree_with_root(node)) {
 291                                 // type coersion for easier access
 292                                 TreeData *data = node->data;
 293
 294                                 // select root and initialize variables
 295                                 if (!selected_root) {
 296                                         selected_root = true;
 297                                         root = data->root;
 298                                 }
 299
 300                                 // check whether root matches
 301                                 if (v3s32_equals(root, data->root)) {
 302                                         // remember position
 303                                         array_apd(&positions, &pos);
 304
 305                                         // remember chunk - unless it's already on the list
 306                                         if (!locked_before)
 307                                                 array_apd(&chunks, &chunk);
 308
 309                                         // remember index was selected
 310                                         selected[i] = true;
 311
 312                                         // don't run rest of loop body to not unlock chunk
 313                                         continue;
 314                                 } else {
 315                                         // if it doesn't match selected root, mark as skipped
 316                                         skipped = true;
 317                                         dirs[i] = false;
 318                                 }
 319                         }
 320
 321                         // only unlock if it wasn't locked before
 322                         if (!locked_before)
 323                                 pthread_rwlock_unlock(&chunk->lock);
 324                 }
 325
 326                 if (selected_root) {
 327                         // run depth search
 328                         if (!check_tree(root, &positions, &chunks)) {
 329                                 // a return value of false means a deadlock occured (should be very rare)
 330                                 printf("[verbose] tree_physics detected deadlock (this not an issue, but should not happen frequently)\n");
 331
 332                                 // sleep for 50ms to hopefully resolve the conflict
 333                                 nanosleep(&(struct timespec) {0, 50e6}, NULL);
 334
 335                                 // invalidate faces that were selected in this iteration
 336                                 for (int i = 0; i < 6; i++)
 337                                         if (selected[i])
 338                                                 dirs[i] = false;
 339                         }
 340
 341                         // free memory
 342                         array_clr(&positions);
 343                         array_clr(&chunks);
 344                 }
 345
 346         // repeat until all directions have been processed
 347         } while (skipped);
 348 }