Changeset b826e6b for src/libcfa/concurrency/kernel.c

Timestamp:

Jul 19, 2017, 11:49:33 AM (8 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

9cc0472

Parents:

fea3faa (diff), a57cb58 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• src/libcfa/concurrency/kernel.c (modified) (35 diffs)

src/libcfa/concurrency/kernel.c

@@ -15 +15 @@
 //
 
-#include "startup.h"
-
-//Start and stop routine for the kernel, declared first to make sure they run first
-void kernel_startup(void)  __attribute__(( constructor( STARTUP_PRIORITY_KERNEL ) ));
-void kernel_shutdown(void) __attribute__(( destructor ( STARTUP_PRIORITY_KERNEL ) ));
-
-//Header
-#include "kernel_private.h"
+#include "libhdr.h"
 
 //C Includes
@@ -35 +28 @@
 
 //CFA Includes
-#include "libhdr.h"
+#include "kernel_private.h"
 #include "preemption.h"
+#include "startup.h"
 
 //Private includes
@@ -42 +36 @@
 #include "invoke.h"
 
+//Start and stop routine for the kernel, declared first to make sure they run first
+void kernel_startup(void)  __attribute__(( constructor( STARTUP_PRIORITY_KERNEL ) ));
+void kernel_shutdown(void) __attribute__(( destructor ( STARTUP_PRIORITY_KERNEL ) ));
+
 //-----------------------------------------------------------------------------
 // Kernel storage
-#define KERNEL_STORAGE(T,X) static char X##_storage[sizeof(T)]
-
-KERNEL_STORAGE(processorCtx_t, systemProcessorCtx);
-KERNEL_STORAGE(cluster, systemCluster);
-KERNEL_STORAGE(system_proc_t, systemProcessor);
-KERNEL_STORAGE(thread_desc, mainThread);
-KERNEL_STORAGE(machine_context_t, mainThread_context);
-
-cluster * systemCluster;
-system_proc_t * systemProcessor;
+KERNEL_STORAGE(cluster,           mainCluster);
+KERNEL_STORAGE(processor,         mainProcessor);
+KERNEL_STORAGE(processorCtx_t,    mainProcessorCtx);
+KERNEL_STORAGE(thread_desc,       mainThread);
+KERNEL_STORAGE(machine_context_t, mainThreadCtx);
+
+cluster *     mainCluster;
+processor *   mainProcessor;
 thread_desc * mainThread;
 
@@ -59 +55 @@
 // Global state
 
-thread_local processor * this_processor;
-
-coroutine_desc * this_coroutine(void) {
-        return this_processor->current_coroutine;
-}
-
-thread_desc * this_thread(void) {
-        return this_processor->current_thread;
-}
+volatile thread_local coroutine_desc * this_coroutine;
+volatile thread_local thread_desc * this_thread;
+volatile thread_local processor * this_processor;
+
+volatile thread_local bool preemption_in_progress = 0;
+volatile thread_local unsigned short disable_preempt_count = 1;
 
 //-----------------------------------------------------------------------------
 // Main thread construction
 struct current_stack_info_t {
-        machine_context_t ctx;  
+        machine_context_t ctx;
         unsigned int size;              // size of stack
         void *base;                             // base of stack
@@ -82 +75 @@
 
 void ?{}( current_stack_info_t * this ) {
-        CtxGet( &this->ctx );
+        CtxGet( this->ctx );
         this->base = this->ctx.FP;
         this->storage = this->ctx.SP;
@@ -91 +84 @@
 
         this->limit = (void *)(((intptr_t)this->base) - this->size);
-        this->context = &mainThread_context_storage;
+        this->context = &storage_mainThreadCtx;
         this->top = this->base;
 }
@@ -106 +99 @@
 
 void ?{}( coroutine_desc * this, current_stack_info_t * info) {
-        (&this->stack){ info }; 
+        (&this->stack){ info };
         this->name = "Main Thread";
         this->errno_ = 0;
@@ -131 +124 @@
 
 void ?{}(processor * this) {
-        this{ systemCluster };
+        this{ mainCluster };
 }
 
 void ?{}(processor * this, cluster * cltr) {
         this->cltr = cltr;
-        this->current_coroutine = NULL;
-        this->current_thread = NULL;
-        (&this->terminated){};
-        this->is_terminated = false;
+        (&this->terminated){ 0 };
+        this->do_terminate = false;
         this->preemption_alarm = NULL;
-        this->preemption = default_preemption();
-        this->disable_preempt_count = 1;                //Start with interrupts disabled
         this->pending_preemption = false;
 
@@ -150 +139 @@
 void ?{}(processor * this, cluster * cltr, processorCtx_t * runner) {
         this->cltr = cltr;
-        this->current_coroutine = NULL;
-        this->current_thread = NULL;
-        (&this->terminated){};
-        this->is_terminated = false;
-        this->disable_preempt_count = 0;
+        (&this->terminated){ 0 };
+        this->do_terminate = false;
+        this->preemption_alarm = NULL;
         this->pending_preemption = false;
+        this->kernel_thread = pthread_self();
 
         this->runner = runner;
-        LIB_DEBUG_PRINT_SAFE("Kernel : constructing processor context %p\n", runner);
+        LIB_DEBUG_PRINT_SAFE("Kernel : constructing main processor context %p\n", runner);
         runner{ this };
 }
 
-void ?{}(system_proc_t * this, cluster * cltr, processorCtx_t * runner) {
-        (&this->alarms){};
-        (&this->alarm_lock){};
-        this->pending_alarm = false;
-
-        (&this->proc){ cltr, runner };
-}
-
 void ^?{}(processor * this) {
-        if( ! this->is_terminated ) {
+        if( ! this->do_terminate ) {
                 LIB_DEBUG_PRINT_SAFE("Kernel : core %p signaling termination\n", this);
-                this->is_terminated = true;
-                wait( &this->terminated );
+                this->do_terminate = true;
+                P( &this->terminated );
+                pthread_join( this->kernel_thread, NULL );
         }
 }
@@ -180 +161 @@
 void ?{}(cluster * this) {
         ( &this->ready_queue ){};
-        ( &this->lock ){};
+        ( &this->ready_queue_lock ){};
+
+        this->preemption = default_preemption();
 }
 
 void ^?{}(cluster * this) {
-        
+
 }
 
@@ -203 +186 @@
 
                 thread_desc * readyThread = NULL;
-                for( unsigned int spin_count = 0; ! this->is_terminated; spin_count++ ) 
+                for( unsigned int spin_count = 0; ! this->do_terminate; spin_count++ )
                 {
                         readyThread = nextThread( this->cltr );
@@ -209 +192 @@
                         if(readyThread)
                         {
+                                verify( disable_preempt_count > 0 );
+
                                 runThread(this, readyThread);
+
+                                verify( disable_preempt_count > 0 );
 
                                 //Some actions need to be taken from the kernel
@@ -225 +212 @@
         }
 
-        signal( &this->terminated );
+        V( &this->terminated );
+
         LIB_DEBUG_PRINT_SAFE("Kernel : core %p terminated\n", this);
 }
 
-// runThread runs a thread by context switching 
-// from the processor coroutine to the target thread 
+// runThread runs a thread by context switching
+// from the processor coroutine to the target thread
 void runThread(processor * this, thread_desc * dst) {
         coroutine_desc * proc_cor = get_coroutine(this->runner);
         coroutine_desc * thrd_cor = get_coroutine(dst);
-        
+
         //Reset the terminating actions here
         this->finish.action_code = No_Action;
 
         //Update global state
-        this->current_thread = dst;
+        this_thread = dst;
 
         // Context Switch to the thread
@@ -246 +234 @@
 }
 
-// Once a thread has finished running, some of 
+// Once a thread has finished running, some of
 // its final actions must be executed from the kernel
 void finishRunning(processor * this) {
@@ -256 +244 @@
         }
         else if( this->finish.action_code == Release_Schedule ) {
-                unlock( this->finish.lock );            
+                unlock( this->finish.lock );
                 ScheduleThread( this->finish.thrd );
         }
@@ -289 +277 @@
         processor * proc = (processor *) arg;
         this_processor = proc;
+        this_coroutine = NULL;
+        this_thread = NULL;
+        disable_preempt_count = 1;
         // SKULLDUGGERY: We want to create a context for the processor coroutine
         // which is needed for the 2-step context switch. However, there is no reason
-        // to waste the perfectly valid stack create by pthread. 
+        // to waste the perfectly valid stack create by pthread.
         current_stack_info_t info;
         machine_context_t ctx;
@@ -300 +291 @@
 
         //Set global state
-        proc->current_coroutine = &proc->runner->__cor;
-        proc->current_thread = NULL;
+        this_coroutine = &proc->runner->__cor;
+        this_thread = NULL;
 
         //We now have a proper context from which to schedule threads
         LIB_DEBUG_PRINT_SAFE("Kernel : core %p created (%p, %p)\n", proc, proc->runner, &ctx);
 
-        // SKULLDUGGERY: Since the coroutine doesn't have its own stack, we can't 
-        // resume it to start it like it normally would, it will just context switch 
-        // back to here. Instead directly call the main since we already are on the 
+        // SKULLDUGGERY: Since the coroutine doesn't have its own stack, we can't
+        // resume it to start it like it normally would, it will just context switch
+        // back to here. Instead directly call the main since we already are on the
         // appropriate stack.
         proc_cor_storage.__cor.state = Active;
@@ -315 +306 @@
 
         // Main routine of the core returned, the core is now fully terminated
-        LIB_DEBUG_PRINT_SAFE("Kernel : core %p main ended (%p)\n", proc, proc->runner); 
+        LIB_DEBUG_PRINT_SAFE("Kernel : core %p main ended (%p)\n", proc, proc->runner);
 
         return NULL;
@@ -322 +313 @@
 void start(processor * this) {
         LIB_DEBUG_PRINT_SAFE("Kernel : Starting core %p\n", this);
-        
+
         pthread_create( &this->kernel_thread, NULL, CtxInvokeProcessor, (void*)this );
 
-        LIB_DEBUG_PRINT_SAFE("Kernel : core %p started\n", this);       
+        LIB_DEBUG_PRINT_SAFE("Kernel : core %p started\n", this);
 }
 
@@ -331 +322 @@
 // Scheduler routines
 void ScheduleThread( thread_desc * thrd ) {
-        if( !thrd ) return;
+        // if( !thrd ) return;
+        assert( thrd );
+        assert( thrd->cor.state != Halted );
+
+        verify( disable_preempt_count > 0 );
 
         verifyf( thrd->next == NULL, "Expected null got %p", thrd->next );
-        
-        lock( &systemProcessor->proc.cltr->lock );
-        append( &systemProcessor->proc.cltr->ready_queue, thrd );
-        unlock( &systemProcessor->proc.cltr->lock );
+
+        lock(   &this_processor->cltr->ready_queue_lock DEBUG_CTX2 );
+        append( &this_processor->cltr->ready_queue, thrd );
+        unlock( &this_processor->cltr->ready_queue_lock );
+
+        verify( disable_preempt_count > 0 );
 }
 
 thread_desc * nextThread(cluster * this) {
-        lock( &this->lock );
+        verify( disable_preempt_count > 0 );
+        lock( &this->ready_queue_lock DEBUG_CTX2 );
         thread_desc * head = pop_head( &this->ready_queue );
-        unlock( &this->lock );
+        unlock( &this->ready_queue_lock );
+        verify( disable_preempt_count > 0 );
         return head;
 }
 
-void ScheduleInternal() {
-        suspend();
-}
-
-void ScheduleInternal( spinlock * lock ) {
+void BlockInternal() {
+        disable_interrupts();
+        verify( disable_preempt_count > 0 );
+        suspend();
+        verify( disable_preempt_count > 0 );
+        enable_interrupts( DEBUG_CTX );
+}
+
+void BlockInternal( spinlock * lock ) {
+        disable_interrupts();
         this_processor->finish.action_code = Release;
         this_processor->finish.lock = lock;
-        suspend();
-}
-
-void ScheduleInternal( thread_desc * thrd ) {
+
+        verify( disable_preempt_count > 0 );
+        suspend();
+        verify( disable_preempt_count > 0 );
+
+        enable_interrupts( DEBUG_CTX );
+}
+
+void BlockInternal( thread_desc * thrd ) {
+        disable_interrupts();
+        assert( thrd->cor.state != Halted );
         this_processor->finish.action_code = Schedule;
         this_processor->finish.thrd = thrd;
-        suspend();
-}
-
-void ScheduleInternal( spinlock * lock, thread_desc * thrd ) {
+
+        verify( disable_preempt_count > 0 );
+        suspend();
+        verify( disable_preempt_count > 0 );
+
+        enable_interrupts( DEBUG_CTX );
+}
+
+void BlockInternal( spinlock * lock, thread_desc * thrd ) {
+        disable_interrupts();
         this_processor->finish.action_code = Release_Schedule;
         this_processor->finish.lock = lock;
         this_processor->finish.thrd = thrd;
-        suspend();
-}
-
-void ScheduleInternal(spinlock ** locks, unsigned short count) {
+
+        verify( disable_preempt_count > 0 );
+        suspend();
+        verify( disable_preempt_count > 0 );
+
+        enable_interrupts( DEBUG_CTX );
+}
+
+void BlockInternal(spinlock ** locks, unsigned short count) {
+        disable_interrupts();
         this_processor->finish.action_code = Release_Multi;
         this_processor->finish.locks = locks;
         this_processor->finish.lock_count = count;
-        suspend();
-}
-
-void ScheduleInternal(spinlock ** locks, unsigned short lock_count, thread_desc ** thrds, unsigned short thrd_count) {
+
+        verify( disable_preempt_count > 0 );
+        suspend();
+        verify( disable_preempt_count > 0 );
+
+        enable_interrupts( DEBUG_CTX );
+}
+
+void BlockInternal(spinlock ** locks, unsigned short lock_count, thread_desc ** thrds, unsigned short thrd_count) {
+        disable_interrupts();
         this_processor->finish.action_code = Release_Multi_Schedule;
         this_processor->finish.locks = locks;
@@ -383 +412 @@
         this_processor->finish.thrds = thrds;
         this_processor->finish.thrd_count = thrd_count;
+
+        verify( disable_preempt_count > 0 );
+        suspend();
+        verify( disable_preempt_count > 0 );
+
+        enable_interrupts( DEBUG_CTX );
+}
+
+void LeaveThread(spinlock * lock, thread_desc * thrd) {
+        verify( disable_preempt_count > 0 );
+        this_processor->finish.action_code = thrd ? Release_Schedule : Release;
+        this_processor->finish.lock = lock;
+        this_processor->finish.thrd = thrd;
+
         suspend();
 }
@@ -392 +435 @@
 // Kernel boot procedures
 void kernel_startup(void) {
-        LIB_DEBUG_PRINT_SAFE("Kernel : Starting\n");    
+        LIB_DEBUG_PRINT_SAFE("Kernel : Starting\n");
 
         // Start by initializing the main thread
-        // SKULLDUGGERY: the mainThread steals the process main thread 
-        // which will then be scheduled by the systemProcessor normally
-        mainThread = (thread_desc *)&mainThread_storage;
+        // SKULLDUGGERY: the mainThread steals the process main thread
+        // which will then be scheduled by the mainProcessor normally
+        mainThread = (thread_desc *)&storage_mainThread;
         current_stack_info_t info;
         mainThread{ &info };
@@ -403 +446 @@
         LIB_DEBUG_PRINT_SAFE("Kernel : Main thread ready\n");
 
+        // Initialize the main cluster
+        mainCluster = (cluster *)&storage_mainCluster;
+        mainCluster{};
+
+        LIB_DEBUG_PRINT_SAFE("Kernel : main cluster ready\n");
+
+        // Initialize the main processor and the main processor ctx
+        // (the coroutine that contains the processing control flow)
+        mainProcessor = (processor *)&storage_mainProcessor;
+        mainProcessor{ mainCluster, (processorCtx_t *)&storage_mainProcessorCtx };
+
+        //initialize the global state variables
+        this_processor = mainProcessor;
+        this_thread = mainThread;
+        this_coroutine = &mainThread->cor;
+
         // Enable preemption
         kernel_start_preemption();
 
-        // Initialize the system cluster
-        systemCluster = (cluster *)&systemCluster_storage;
-        systemCluster{};
-
-        LIB_DEBUG_PRINT_SAFE("Kernel : System cluster ready\n");
-
-        // Initialize the system processor and the system processor ctx
-        // (the coroutine that contains the processing control flow)
-        systemProcessor = (system_proc_t *)&systemProcessor_storage;
-        systemProcessor{ systemCluster, (processorCtx_t *)&systemProcessorCtx_storage };
-
-        // Add the main thread to the ready queue 
-        // once resume is called on systemProcessor->runner the mainThread needs to be scheduled like any normal thread
+        // Add the main thread to the ready queue
+        // once resume is called on mainProcessor->runner the mainThread needs to be scheduled like any normal thread
         ScheduleThread(mainThread);
 
-        //initialize the global state variables
-        this_processor = &systemProcessor->proc;
-        this_processor->current_thread = mainThread;
-        this_processor->current_coroutine = &mainThread->cor;
-
-        // SKULLDUGGERY: Force a context switch to the system processor to set the main thread's context to the current UNIX
+        // SKULLDUGGERY: Force a context switch to the main processor to set the main thread's context to the current UNIX
         // context. Hence, the main thread does not begin through CtxInvokeThread, like all other threads. The trick here is that
-        // mainThread is on the ready queue when this call is made. 
-        resume( systemProcessor->proc.runner );
+        // mainThread is on the ready queue when this call is made.
+        resume( mainProcessor->runner );
 
 
@@ -435 +478 @@
         // THE SYSTEM IS NOW COMPLETELY RUNNING
         LIB_DEBUG_PRINT_SAFE("Kernel : Started\n--------------------------------------------------\n\n");
+
+        enable_interrupts( DEBUG_CTX );
 }
 
@@ -440 +485 @@
         LIB_DEBUG_PRINT_SAFE("\n--------------------------------------------------\nKernel : Shutting down\n");
 
-        // SKULLDUGGERY: Notify the systemProcessor it needs to terminates.
+        disable_interrupts();
+
+        // SKULLDUGGERY: Notify the mainProcessor it needs to terminates.
         // When its coroutine terminates, it return control to the mainThread
         // which is currently here
-        systemProcessor->proc.is_terminated = true;
+        mainProcessor->do_terminate = true;
         suspend();
 
         // THE SYSTEM IS NOW COMPLETELY STOPPED
 
-        // Destroy the system processor and its context in reverse order of construction
+        // Disable preemption
+        kernel_stop_preemption();
+
+        // Destroy the main processor and its context in reverse order of construction
         // These were manually constructed so we need manually destroy them
-        ^(systemProcessor->proc.runner){};
-        ^(systemProcessor){};
+        ^(mainProcessor->runner){};
+        ^(mainProcessor){};
 
         // Final step, destroy the main thread since it is no longer needed
@@ -457 +507 @@
         ^(mainThread){};
 
-        LIB_DEBUG_PRINT_SAFE("Kernel : Shutdown complete\n");   
+        LIB_DEBUG_PRINT_SAFE("Kernel : Shutdown complete\n");
 }
 
@@ -467 +517 @@
         // abort cannot be recursively entered by the same or different processors because all signal handlers return when
         // the globalAbort flag is true.
-        lock( &kernel_abort_lock );
+        lock( &kernel_abort_lock DEBUG_CTX2 );
 
         // first task to abort ?
@@ -473 +523 @@
                 kernel_abort_called = true;
                 unlock( &kernel_abort_lock );
-        } 
+        }
         else {
                 unlock( &kernel_abort_lock );
-                
+
                 sigset_t mask;
                 sigemptyset( &mask );
@@ -482 +532 @@
                 sigaddset( &mask, SIGUSR1 );                    // block SIGUSR1 signals
                 sigsuspend( &mask );                            // block the processor to prevent further damage during abort
-                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it              
-        }
-
-        return this_thread();
+                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it
+        }
+
+        return this_thread;
 }
 
@@ -494 +544 @@
         __lib_debug_write( STDERR_FILENO, abort_text, len );
 
-        if ( thrd != this_coroutine() ) {
-                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine()->name, this_coroutine() );
+        if ( thrd != this_coroutine ) {
+                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine->name, this_coroutine );
                 __lib_debug_write( STDERR_FILENO, abort_text, len );
-        } 
+        }
         else {
                 __lib_debug_write( STDERR_FILENO, ".\n", 2 );
@@ -505 +555 @@
 extern "C" {
         void __lib_debug_acquire() {
-                lock(&kernel_debug_lock);
+                lock( &kernel_debug_lock DEBUG_CTX2 );
         }
 
         void __lib_debug_release() {
-                unlock(&kernel_debug_lock);
+                unlock( &kernel_debug_lock );
         }
 }
@@ -525 +575 @@
 }
 
-bool try_lock( spinlock * this ) {
+bool try_lock( spinlock * this DEBUG_CTX_PARAM2 ) {
         return this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0;
 }
 
-void lock( spinlock * this ) {
+void lock( spinlock * this DEBUG_CTX_PARAM2 ) {
         for ( unsigned int i = 1;; i += 1 ) {
-                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) break;
-        }
-}
+                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) { break; }
+        }
+        LIB_DEBUG_DO(
+                this->prev_name = caller;
+                this->prev_thrd = this_thread;
+        )
+}
+
+void lock_yield( spinlock * this DEBUG_CTX_PARAM2 ) {
+        for ( unsigned int i = 1;; i += 1 ) {
+                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) { break; }
+                yield();
+        }
+        LIB_DEBUG_DO(
+                this->prev_name = caller;
+                this->prev_thrd = this_thread;
+        )
+}
+
 
 void unlock( spinlock * this ) {
@@ -539 +605 @@
 }
 
-void ?{}( signal_once * this ) {
-        this->cond = false;
-}
-void ^?{}( signal_once * this ) {
-
-}
-
-void wait( signal_once * this ) {
-        lock( &this->lock );
-        if( !this->cond ) {
-                append( &this->blocked, this_thread() );
-                ScheduleInternal( &this->lock );
-                lock( &this->lock );
-        }
+void  ?{}( semaphore * this, int count = 1 ) {
+        (&this->lock){};
+        this->count = count;
+        (&this->waiting){};
+}
+void ^?{}(semaphore * this) {}
+
+void P(semaphore * this) {
+        lock( &this->lock DEBUG_CTX2 );
+        this->count -= 1;
+        if ( this->count < 0 ) {
+                // queue current task
+                append( &this->waiting, (thread_desc *)this_thread );
+
+                // atomically release spin lock and block
+                BlockInternal( &this->lock );
+        }
+        else {
+            unlock( &this->lock );
+        }
+}
+
+void V(semaphore * this) {
+        thread_desc * thrd = NULL;
+        lock( &this->lock DEBUG_CTX2 );
+        this->count += 1;
+        if ( this->count <= 0 ) {
+                // remove task at head of waiting list
+                thrd = pop_head( &this->waiting );
+        }
+
         unlock( &this->lock );
-}
-
-void signal( signal_once * this ) {
-        lock( &this->lock );
-        {
-                this->cond = true;
-
-                thread_desc * it;
-                while( it = pop_head( &this->blocked) ) {
-                        ScheduleThread( it );
-                }
-        }
-        unlock( &this->lock );
+
+        // make new owner
+        WakeThread( thrd );
 }
 
@@ -590 +663 @@
                 }
                 head->next = NULL;
-        }       
+        }
         return head;
 }
@@ -609 +682 @@
                 this->top = top->next;
                 top->next = NULL;
-        }       
+        }
         return top;
 }