Kernel/vfs/select.c

   1 /*
   2  * Acess2 VFS
   3  * - By thePowersGang (John Hodge)
   4  *
   5  * select.c
   6  * - Implements the select() system call (and supporting code)
   7  */
   8 #define DEBUG   0
   9 #include <acess.h>
  10 #include "vfs.h"
  11 #include "vfs_int.h"
  12 #include "vfs_ext.h"
  13 #include <semaphore.h>
  14
  15 // === CONSTANTS ===
  16 #define NUM_THREADS_PER_ALLOC   4
  17
  18 // === TYPES ===
  19 typedef struct sVFS_SelectThread        tVFS_SelectThread;
  20 typedef struct sVFS_SelectListEnt       tVFS_SelectListEnt;
  21
  22 // === STRUCTURES ===
  23 struct sVFS_SelectListEnt
  24 {
  25         tVFS_SelectListEnt      *Next;
  26         tVFS_SelectThread       *Threads[NUM_THREADS_PER_ALLOC];
  27 };
  28
  29 struct sVFS_SelectList
  30 {
  31         tMutex  Lock;
  32         tVFS_SelectListEnt      FirstEnt;
  33 };
  34
  35 struct sVFS_SelectThread
  36 {
  37         //! \brief Semaphore to atomically put the listener to sleep
  38         tSemaphore      SleepHandle;    // TODO: Allow timeouts (by setting an alarm?)
  39 };
  40
  41 // === PROTOTYPES ===
  42 // int  VFS_SelectNode(tVFS_Node *Node, enum eVFS_SelectTypes Type, tTime *Timeout);
  43 // int  VFS_Select(int MaxHandle, fd_set *ReadHandles, fd_set *WriteHandles, fd_set *ErrHandles, tTime *Timeout, BOOL IsKernel);
  44 // int  VFS_MarkFull(tVFS_Node *Node, BOOL IsBufferFull);
  45 // int  VFS_MarkAvaliable(tVFS_Node *Node, BOOL IsDataAvaliable);
  46 // int  VFS_MarkError(tVFS_Node *Node, BOOL IsErrorState);
  47  int    VFS_int_Select_GetType(enum eVFS_SelectTypes Type, tVFS_Node *Node, tVFS_SelectList ***List, int **Flag, int *WantedFlag, int *MaxAllowed);
  48  int    VFS_int_Select_Register(tVFS_SelectThread *Thread, int MaxHandle, fd_set *Handles, enum eVFS_SelectTypes Type, BOOL IsKernel);
  49  int    VFS_int_Select_Deregister(tVFS_SelectThread *Thread, int MaxHandle, fd_set *Handles, enum eVFS_SelectTypes Type, BOOL IsKernel);
  50  int    VFS_int_Select_AddThread(tVFS_SelectList *List, tVFS_SelectThread *Thread, int MaxAllowed);
  51 void    VFS_int_Select_RemThread(tVFS_SelectList *List, tVFS_SelectThread *Thread);
  52 void    VFS_int_Select_SignalAll(tVFS_SelectList *List);
  53
  54 // === GLOBALS ===
  55
  56 // === FUNCTIONS ===
  57 int VFS_SelectNode(tVFS_Node *Node, enum eVFS_SelectTypes Type, tTime *Timeout)
  58 {
  59         tVFS_SelectThread       *thread_info;
  60         tVFS_SelectList **list;
  61          int    *flag, wanted, maxAllowed;
  62
  63         ENTER("pNode iType pTimeout", Node, Type, Timeout);
  64
  65         if( VFS_int_Select_GetType(Type, Node, &list, &flag, &wanted, &maxAllowed) ) {
  66                 LEAVE('i', -1);
  67                 return -1;
  68         }
  69
  70         thread_info = malloc(sizeof(tVFS_SelectThread));
  71         if(!thread_info)        return -1;
  72
  73         Semaphore_Init(&thread_info->SleepHandle, 0, 0, "VFS_SelectNode()", "");
  74
  75         LOG("list=%p, flag=%p, wanted=%i, maxAllowed=%i", list, flag, wanted, maxAllowed);
  76
  77         // Alloc if needed
  78         if( !*list ) {
  79                 *list = calloc(1, sizeof(tVFS_SelectList));
  80         }
  81
  82         VFS_int_Select_AddThread(*list, thread_info, maxAllowed);
  83         if( *flag == wanted )
  84         {
  85                 VFS_int_Select_RemThread(*list, thread_info);
  86                 free(thread_info);
  87                 LEAVE('i', 1);
  88                 return 1;
  89         }
  90
  91         if( !Timeout || *Timeout > 0 )
  92         {
  93                 LOG("Semaphore_Wait()");
  94                 // TODO: Actual timeout
  95                 Semaphore_Wait(&thread_info->SleepHandle, 1);
  96         }
  97
  98         LOG("VFS_int_Select_RemThread()");
  99         VFS_int_Select_RemThread(*list, thread_info);
 100
 101         free(thread_info);
 102
 103         LEAVE('i', *flag == wanted);
 104         return *flag == wanted;
 105 }
 106
 107 int VFS_Select(int MaxHandle, fd_set *ReadHandles, fd_set *WriteHandles, fd_set *ErrHandles, tTime *Timeout, BOOL IsKernel)
 108 {
 109         tVFS_SelectThread       *thread_info;
 110          int    ret;
 111
 112         thread_info = malloc(sizeof(tVFS_SelectThread));
 113         if(!thread_info)        return -1;
 114
 115         Semaphore_Init(&thread_info->SleepHandle, 0, -1, "VFS_Select()", "");
 116
 117         // Notes: The idea is to make sure we onlt enter wait (on the semaphore)
 118         // if we are going to be woken up (either by an event at a later time,
 119         // or by an event that happened while or before we were registering).
 120         // Hence, register must happen _before_ we check the state flag
 121         // (See VFS_int_Select_Register), that way either we pick up the flag,
 122         // or the semaphore is incremeneted (or both, but never none)
 123
 124         // Register with nodes
 125         ret  = VFS_int_Select_Register(thread_info, MaxHandle, ReadHandles, 0, IsKernel);
 126         ret += VFS_int_Select_Register(thread_info, MaxHandle, WriteHandles, 1, IsKernel);
 127         ret += VFS_int_Select_Register(thread_info, MaxHandle, ErrHandles, 2, IsKernel);
 128
 129         // If there were events waiting, de-register and return
 130         if( ret )
 131         {
 132                 ret  = VFS_int_Select_Deregister(thread_info, MaxHandle, ReadHandles, 0, IsKernel);
 133                 ret += VFS_int_Select_Deregister(thread_info, MaxHandle, WriteHandles, 1, IsKernel);
 134                 ret += VFS_int_Select_Deregister(thread_info, MaxHandle, ErrHandles, 2, IsKernel);
 135                 free(thread_info);
 136                 return ret;
 137         }
 138
 139         // TODO: Implement timeout
 140
 141         // Wait (only if there is no timeout, or it is greater than zero
 142         if( !Timeout || *Timeout > 0 )
 143         {
 144                 ret = Semaphore_Wait(&thread_info->SleepHandle, 1);
 145         }
 146
 147         // Fill output (modify *Handles)
 148         // - Also, de-register
 149         ret  = VFS_int_Select_Deregister(thread_info, MaxHandle, ReadHandles, 0, IsKernel);
 150         ret += VFS_int_Select_Deregister(thread_info, MaxHandle, WriteHandles, 1, IsKernel);
 151         ret += VFS_int_Select_Deregister(thread_info, MaxHandle, ErrHandles, 2, IsKernel);
 152         free(thread_info);
 153         return ret;
 154 }
 155
 156 // Mark a node as having data ready for reading
 157 int VFS_MarkAvaliable(tVFS_Node *Node, BOOL IsDataAvaliable)
 158 {
 159         ENTER("pNode bIsDataAvaliable", Node, IsDataAvaliable);
 160         Node->DataAvaliable = !!IsDataAvaliable;
 161         if( Node->DataAvaliable )
 162                 VFS_int_Select_SignalAll(Node->ReadThreads);
 163         LEAVE('i', 0);
 164         return 0;
 165 }
 166
 167 // Mark a node as having a full buffer
 168 int VFS_MarkFull(tVFS_Node *Node, BOOL IsBufferFull)
 169 {
 170         ENTER("pNode bIsDataAvaliable", Node, IsBufferFull);
 171         Node->BufferFull = !!IsBufferFull;
 172         if( !Node->BufferFull )
 173                 VFS_int_Select_SignalAll(Node->WriteThreads);
 174         LEAVE('i', 0);
 175         return 0;
 176 }
 177
 178 // Mark a node as errored
 179 int VFS_MarkError(tVFS_Node *Node, BOOL IsErrorState)
 180 {
 181         ENTER("pNode bIsDataAvaliable", Node, IsErrorState);
 182         Node->ErrorOccurred = !!IsErrorState;
 183         if( Node->ErrorOccurred )
 184                 VFS_int_Select_SignalAll(Node->ErrorThreads);
 185         LEAVE('i', 0);
 186         return 0;
 187 }
 188
 189 // --- Internal ---
 190 int VFS_int_Select_GetType(enum eVFS_SelectTypes Type, tVFS_Node *Node, tVFS_SelectList ***List, int **Flag, int *WantedFlag, int *MaxAllowed)
 191 {
 192         // Get the type of the listen
 193         switch(Type)
 194         {
 195         case 0: // Read
 196                 if(List)        *List = &Node->ReadThreads;
 197                 if(Flag)        *Flag = &Node->DataAvaliable;
 198                 if(WantedFlag)  *WantedFlag = 1;
 199                 if(MaxAllowed)  *MaxAllowed = 1;        // Max of 1 for read
 200                 break;
 201         case 1: // Write
 202                 if(List)        *List = &Node->WriteThreads;
 203                 if(Flag)        *Flag = &Node->BufferFull;
 204                 if(WantedFlag)  *WantedFlag = 0;
 205                 if(MaxAllowed)  *MaxAllowed = 1;        // Max of 1 for write
 206                 break;
 207         case 2: // Error
 208                 if(List)        *List = &Node->ErrorThreads;
 209                 if(Flag)        *Flag = &Node->ErrorOccurred;
 210                 if(WantedFlag)  *WantedFlag = 1;
 211                 if(MaxAllowed)  *MaxAllowed = -1;       // No max for error listeners
 212                 break;
 213         default:
 214                 Log_Error("VFS", "VFS_int_Select_GetType: BUG CHECK, Unknown Type %i", Type);
 215                 return 1;
 216         }
 217         return 0;
 218 }
 219
 220 /**
 221  * \return Number of files with an action
 222  */
 223 int VFS_int_Select_Register(tVFS_SelectThread *Thread, int MaxHandle, fd_set *Handles, enum eVFS_SelectTypes Type, BOOL IsKernel)
 224 {
 225          int    i, numFlagged = 0;
 226         tVFS_SelectList **list;
 227          int    *flag, wantedFlagValue;
 228          int    maxAllowed;
 229
 230         if( !Handles )  return 0;
 231
 232         ENTER("pThread iMaxHandle pHandles iType BIsKernel", Thread, MaxHandle, Handles, Type, IsKernel);
 233
 234         for( i = 0; i < MaxHandle; i ++ )
 235         {
 236                 tVFS_Handle     *handle;
 237
 238                 // Is the descriptor set
 239                 if( !FD_ISSET(i, Handles) )     continue;
 240
 241                 handle = VFS_GetHandle( i | (IsKernel?VFS_KERNEL_FLAG:0) );
 242                 // Is the handle valid?
 243                 if( !handle || !handle->Node )
 244                 {
 245                         if( Type == 2 ) {       // Bad FD counts as an error
 246                                 numFlagged ++;
 247                         }
 248                         else {
 249                                 FD_CLR(i, Handles);
 250                         }
 251                         continue;
 252                 }
 253
 254                 // Get the type of the listen
 255                 if( VFS_int_Select_GetType(Type, handle->Node, &list, &flag, &wantedFlagValue, &maxAllowed) ) {
 256                         LEAVE('i', 0);
 257                         return 0;
 258                 }
 259
 260                 // Alloc if needed
 261                 if( !*list ) {
 262                         *list = calloc(1, sizeof(tVFS_SelectList));
 263                 }
 264
 265                 // Register
 266                 if( VFS_int_Select_AddThread(*list, Thread, maxAllowed ) )
 267                 {
 268                         // Oops, error (or just no space)
 269                         FD_CLR(i, Handles);
 270                 }
 271
 272                 // Check for the flag
 273                 if( !!*flag == !!wantedFlagValue )
 274                         numFlagged ++;
 275         }
 276
 277         LEAVE('i', numFlagged);
 278
 279         return numFlagged;
 280 }
 281 /**
 282  * \return Number of files with an action
 283  */
 284 int VFS_int_Select_Deregister(tVFS_SelectThread *Thread, int MaxHandle, fd_set *Handles, enum eVFS_SelectTypes Type, BOOL IsKernel)
 285 {
 286          int    i, numFlagged = 0;
 287         tVFS_SelectList **list;
 288          int    *flag, wantedFlagValue;
 289
 290         if( !Handles )  return 0;
 291
 292         ENTER("pThread iMaxHandle pHandles iType BIsKernel", Thread, MaxHandle, Handles, Type, IsKernel);
 293
 294         for( i = 0; i < MaxHandle; i ++ )
 295         {
 296                 tVFS_Handle     *handle;
 297
 298                 // Is the descriptor set
 299                 if( !FD_ISSET(i, Handles) )     continue;
 300
 301                 handle = VFS_GetHandle( i | (IsKernel?VFS_KERNEL_FLAG:0) );
 302                 // Is the handle valid?
 303                 if( !handle || !handle->Node )
 304                 {
 305                         if( Type == 2 ) {       // Bad FD counts as an error
 306                                 numFlagged ++;
 307                         }
 308                         else {
 309                                 FD_CLR(i, Handles);
 310                         }
 311                         continue;
 312                 }
 313
 314                 // Get the type of the listen
 315
 316                 // Get the type of the listen
 317                 if( VFS_int_Select_GetType(Type, handle->Node, &list, &flag, &wantedFlagValue, NULL) ) {
 318                         LEAVE('i', 0);
 319                         return 0;
 320                 }
 321
 322                 // Remove
 323                 VFS_int_Select_RemThread(*list, Thread );
 324
 325                 // Check for the flag
 326                 if( !!*flag == !!wantedFlagValue ) {
 327                         numFlagged ++;
 328                 }
 329                 else {
 330                         FD_CLR(i, Handles);
 331                 }
 332         }
 333
 334         LEAVE('i', numFlagged);
 335
 336         return numFlagged;
 337 }
 338
 339 /**
 340  * \return Boolean failure
 341  */
 342 int VFS_int_Select_AddThread(tVFS_SelectList *List, tVFS_SelectThread *Thread, int MaxAllowed)
 343 {
 344          int    i, count = 0;
 345         tVFS_SelectListEnt      *block, *prev;
 346
 347         ENTER("pList pThread iMaxAllowed", List, Thread, MaxAllowed);
 348
 349         // Lock to avoid concurrency issues
 350         Mutex_Acquire(&List->Lock);
 351
 352         block = &List->FirstEnt;
 353
 354         // Look for free space
 355         do
 356         {
 357                 for( i = 0; i < NUM_THREADS_PER_ALLOC; i ++ )
 358                 {
 359                         if( block->Threads[i] == NULL )
 360                         {
 361                                 block->Threads[i] = Thread;
 362                                 Mutex_Release(&List->Lock);
 363                                 LEAVE('i', 0);
 364                                 return 0;
 365                         }
 366                         count ++;
 367                         if( MaxAllowed && count >= MaxAllowed ) {
 368                                 LEAVE('i', 1);
 369                                 return 1;
 370                         }
 371                 }
 372
 373                 prev = block;
 374                 block = block->Next;
 375         } while(block);
 376
 377         LOG("New block");
 378
 379         // Create new block
 380         block = malloc( sizeof(tVFS_SelectListEnt) );
 381         if( !block ) {
 382                 Log_Warning("VFS", "VFS_int_Select_AddThread: malloc() failed");
 383                 Mutex_Release(&List->Lock);
 384                 return -1;
 385         }
 386         block->Next = NULL;
 387         block->Threads[0] = Thread;
 388         for( i = 1; i < NUM_THREADS_PER_ALLOC; i ++ )
 389         {
 390                 block->Threads[i] = NULL;
 391         }
 392
 393         // Add to list
 394         prev->Next = block;
 395
 396         // Release
 397         Mutex_Release(&List->Lock);
 398
 399         LEAVE('i', 0);
 400         return 0;
 401 }
 402
 403 void VFS_int_Select_RemThread(tVFS_SelectList *List, tVFS_SelectThread *Thread)
 404 {
 405          int    i;
 406         tVFS_SelectListEnt      *block, *prev;
 407
 408         ENTER("pList pThread", List, Thread);
 409
 410         // Lock to avoid concurrency issues
 411         Mutex_Acquire(&List->Lock);
 412
 413         block = &List->FirstEnt;
 414
 415         // Look for the thread
 416         do
 417         {
 418                 for( i = 0; i < NUM_THREADS_PER_ALLOC; i ++ )
 419                 {
 420                         if( block->Threads[i] == Thread )
 421                         {
 422                                 block->Threads[i] = NULL;
 423
 424                                 // Check if this block is empty
 425                                 if( block != &List->FirstEnt )
 426                                 {
 427                                         for( i = 0; i < NUM_THREADS_PER_ALLOC; i ++ )
 428                                                 if( block->Threads[i] )
 429                                                         break;
 430                                         // If empty, free it
 431                                         if( i == NUM_THREADS_PER_ALLOC ) {
 432                                                 LOG("Deleting block");
 433                                                 prev->Next = block->Next;
 434                                                 free(block);
 435                                         }
 436                                         //TODO: If not empty, check if it can be merged downwards
 437                                 }
 438
 439                                 Mutex_Release(&List->Lock);
 440                                 LEAVE('-');
 441                                 return ;
 442                         }
 443                 }
 444
 445                 prev = block;
 446                 block = block->Next;
 447         } while(block);
 448
 449         // Not on list, is this an error?
 450
 451         Mutex_Release(&List->Lock);
 452
 453         LOG("Not on list");
 454         LEAVE('-');
 455 }
 456
 457 /**
 458  * \brief Signal all threads on a list
 459  */
 460 void VFS_int_Select_SignalAll(tVFS_SelectList *List)
 461 {
 462          int    i;
 463         tVFS_SelectListEnt      *block;
 464
 465         ENTER("pList", List);
 466
 467         // Lock to avoid concurrency issues
 468         Mutex_Acquire(&List->Lock);
 469
 470         block = &List->FirstEnt;
 471
 472         // Look for the thread
 473         do
 474         {
 475                 for( i = 0; i < NUM_THREADS_PER_ALLOC; i ++ )
 476                 {
 477                         LOG("block->Threads[i] = %p", block->Threads[i]);
 478                         if( block->Threads[i]  )
 479                         {
 480                                 Semaphore_Signal( &block->Threads[i]->SleepHandle, 1 );
 481                         }
 482                 }
 483
 484                 block = block->Next;
 485         } while(block);
 486
 487         Mutex_Release(&List->Lock);
 488
 489         LEAVE('-');
 490 }