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