Fork us on GitHub Follow us on Facebook Follow us on Twitter

Ticket #231: diff

File diff, 11.4 KB (added by Jakub Jermář, 9 years ago)

Diff from changeset:head,377.

  • kernel/arch/ia32/include/atomic.h

    === modified file 'kernel/arch/ia32/include/atomic.h'
     
    100100
    101101static inline atomic_count_t test_and_set(atomic_t *val)
    102102{
    103         atomic_count_t v = 1;
     103        atomic_count_t v = 0xf00dba11UL;
    104104       
    105105        asm volatile (
    106106                "xchgl %[v], %[count]\n"
  • kernel/generic/include/cpu.h

    === modified file 'kernel/generic/include/cpu.h'
     
    3737
    3838#include <mm/tlb.h>
    3939#include <synch/spinlock.h>
     40#include <synch/condvar.h>
    4041#include <proc/scheduler.h>
    4142#include <arch/cpu.h>
    4243#include <arch/context.h>
     
    5960        runq_t rq[RQ_COUNT];
    6061        volatile size_t needs_relink;
    6162
     63#ifdef CONFIG_SMP
     64        condvar_t kcpulb_cv;
     65#endif
     66
    6267        SPINLOCK_DECLARE(timeoutlock);
    6368        link_t timeout_active_head;
    6469
  • kernel/generic/include/synch/spinlock.h

    === modified file 'kernel/generic/include/synch/spinlock.h'
     
    4141#include <atomic.h>
    4242#include <debug.h>
    4343
     44#define LOCK_LOCKED     0xf00dba11UL
     45#define LOCK_UNLOCKED   0xca11b00fUL
     46#define LOCK_MAGIC1     0xdeadca1fUL
     47#define LOCK_MAGIC2     0x0becedadUL
     48
    4449#ifdef CONFIG_SMP
    4550
    4651typedef struct {
     52        unative_t magic1;
    4753        atomic_t val;
     54        unative_t magic2;
     55
     56        atomic_t cnt;
    4857       
    4958#ifdef CONFIG_DEBUG_SPINLOCK
    5059        const char *name;
     
    6776#define SPINLOCK_INITIALIZE_NAME(lock_name, desc_name) \
    6877        spinlock_t lock_name = { \
    6978                .name = desc_name, \
    70                 .val = { 0 } \
     79                .magic1 = LOCK_MAGIC1, \
     80                .magic2 = LOCK_MAGIC2, \
     81                .val = { LOCK_UNLOCKED }, \
     82                .cnt = { 0 } \
    7183        }
    7284
    7385#define SPINLOCK_STATIC_INITIALIZE_NAME(lock_name, desc_name) \
    7486        static spinlock_t lock_name = { \
    7587                .name = desc_name, \
    76                 .val = { 0 } \
     88                .magic1 = LOCK_MAGIC1, \
     89                .magic2 = LOCK_MAGIC2, \
     90                .val = { LOCK_UNLOCKED }, \
     91                .cnt = { 0 } \
    7792        }
    7893
    7994#define spinlock_lock(lock)  spinlock_lock_debug(lock)
     
    103118extern void spinlock_initialize(spinlock_t *lock, const char *name);
    104119extern int spinlock_trylock(spinlock_t *lock);
    105120extern void spinlock_lock_debug(spinlock_t *lock);
    106 
    107 /** Unlock spinlock
    108  *
    109  * Unlock spinlock.
    110  *
    111  * @param sl Pointer to spinlock_t structure.
    112  */
    113 static inline void spinlock_unlock(spinlock_t *lock)
    114 {
    115         ASSERT(atomic_get(&lock->val) != 0);
    116        
    117         /*
    118          * Prevent critical section code from bleeding out this way down.
    119          */
    120         CS_LEAVE_BARRIER();
    121        
    122         atomic_set(&lock->val, 0);
    123         preemption_enable();
    124 }
     121extern void spinlock_unlock(spinlock_t *lock);
    125122
    126123#ifdef CONFIG_DEBUG_SPINLOCK
    127124
  • kernel/generic/src/cpu/cpu.c

    === modified file 'kernel/generic/src/cpu/cpu.c'
     
    5858void cpu_init(void) {
    5959        unsigned int i, j;
    6060       
    61 #ifdef CONFIG_SMP
    6261        if (config.cpu_active == 1) {
    63 #endif /* CONFIG_SMP */
    6462                cpus = (cpu_t *) malloc(sizeof(cpu_t) * config.cpu_count,
    65                                         FRAME_ATOMIC);
     63                    FRAME_ATOMIC);
    6664                if (!cpus)
    6765                        panic("Cannot allocate CPU structures.");
    6866
    69                 /* initialize everything */
     67                /* Initialize everything */
    7068                memsetb(cpus, sizeof(cpu_t) * config.cpu_count, 0);
    7169
    7270                for (i = 0; i < config.cpu_count; i++) {
    73                         cpus[i].stack = (uint8_t *) frame_alloc(STACK_FRAMES, FRAME_KA | FRAME_ATOMIC);
     71                        cpus[i].stack = (uint8_t *) frame_alloc(STACK_FRAMES,
     72                            FRAME_KA | FRAME_ATOMIC);
    7473                       
    7574                        cpus[i].id = i;
    7675                       
    7776                        spinlock_initialize(&cpus[i].lock, "cpu_t.lock");
     77#ifdef CONFIG_SMP
     78                        condvar_initialize(&cpus[i].kcpulb_cv);
     79#endif
    7880
    7981                        for (j = 0; j < RQ_COUNT; j++) {
    80                                 spinlock_initialize(&cpus[i].rq[j].lock, "rq_t.lock");
     82                                spinlock_initialize(&cpus[i].rq[j].lock,
     83                                    "rq_t.lock");
    8184                                list_initialize(&cpus[i].rq[j].rq_head);
    8285                        }
    8386                }
    84                
    85 #ifdef CONFIG_SMP
    8687        }
    87 #endif /* CONFIG_SMP */
    8888
    8989        CPU = &cpus[config.cpu_active - 1];
    9090       
  • kernel/generic/src/proc/scheduler.c

    === modified file 'kernel/generic/src/proc/scheduler.c'
     
    189189        interrupts_enable();
    190190       
    191191        if (atomic_get(&CPU->nrdy) == 0) {
     192#ifdef CONFIG_SMP
     193                condvar_signal(&CPU->kcpulb_cv);
     194#endif
     195
    192196                /*
    193197                 * For there was nothing to run, the CPU goes to sleep
    194198                 * until a hardware interrupt or an IPI comes.
     
    530534}
    531535
    532536#ifdef CONFIG_SMP
     537
     538static int get_cpu_balance(atomic_count_t *);
     539
     540/**
     541 * Calculate the number of threads that will be migrated/stolen from
     542 * other CPU's based on the actual situation.
     543 *
     544 * @param average[out]  Pointer to memory where the average number of threads
     545 *                      per CPU will be stored.
     546 * @return The number of threads that should be migrated by the current CPU.
     547 */
     548int get_cpu_balance(atomic_count_t *average)
     549{
     550        *average = atomic_get(&nrdy) / config.cpu_active + 1;
     551        return *average - atomic_get(&CPU->nrdy);
     552}
     553
    533554/** Load balancing thread
    534555 *
    535556 * SMP load balancing thread, supervising thread supplies
     
    547568        int j;
    548569        int k = 0;
    549570        ipl_t ipl;
     571        mutex_t dummy_lock;
     572        uint32_t backoff_us = 0;
    550573
    551574        /*
    552575         * Detach kcpulb as nobody will call thread_join_timeout() on it.
    553576         */
    554577        thread_detach(THREAD);
    555        
     578
     579        /*
     580         * The dummy lock is only needed to indulge the condvar_wait() API,
     581         * but other than that, it is not really necessary. We simply initialize
     582         * it and keep it locked.
     583         */
     584        mutex_initialize(&dummy_lock, MUTEX_PASSIVE);
     585        mutex_lock(&dummy_lock);
     586
    556587loop:
    557         /*
    558          * Work in 1s intervals.
    559          */
    560         thread_sleep(1);
    561 
    562 not_satisfied:
    563         /*
    564          * Calculate the number of threads that will be migrated/stolen from
    565          * other CPU's. Note that situation can have changed between two
    566          * passes. Each time get the most up to date counts.
    567          */
    568         average = atomic_get(&nrdy) / config.cpu_active + 1;
    569         count = average - atomic_get(&CPU->nrdy);
    570 
    571         if (count <= 0)
    572                 goto satisfied;
     588        if (backoff_us)
     589                thread_usleep(backoff_us * 100000);
     590
     591        /*
     592         * Wait until our CPU wants to steal some threads or until a 1s
     593         * interval elapses.
     594         */
     595        while ((count = get_cpu_balance(&average)) <= 0)
     596                condvar_wait_timeout(&CPU->kcpulb_cv, &dummy_lock, 1000000);
     597
     598        if (backoff_us < 1000000)
     599                backoff_us <<= 5;
    573600
    574601        /*
    575602         * Searching least priority queues on all CPU's first and most priority
     
    656683
    657684                                interrupts_restore(ipl);
    658685       
    659                                 if (--count == 0)
    660                                         goto satisfied;
     686                                if (--count == 0) {
     687                                        backoff_us >>= 1;
     688                                        goto loop;
     689                                }
    661690                                       
    662691                                /*
    663692                                 * We are not satisfied yet, focus on another
     
    676705                 * Be a little bit light-weight and let migrated threads run.
    677706                 */
    678707                scheduler();
    679         } else {
    680                 /*
    681                  * We failed to migrate a single thread.
    682                  * Give up this turn.
    683                  */
    684                 goto loop;
     708                backoff_us >>= 1;
    685709        }
    686710               
    687         goto not_satisfied;
    688 
    689 satisfied:
    690711        goto loop;
    691712}
    692713
  • kernel/generic/src/synch/spinlock.c

    === modified file 'kernel/generic/src/synch/spinlock.c'
     
    4343#include <print.h>
    4444#include <debug.h>
    4545#include <symtab.h>
     46#include <cpu.h>
     47#include <proc/thread.h>
     48#include <proc/task.h>
     49#include <arch/cycle.h>
    4650
    4751#ifdef CONFIG_SMP
    4852
     
    5357 */
    5458void spinlock_initialize(spinlock_t *lock, const char *name)
    5559{
    56         atomic_set(&lock->val, 0);
     60        atomic_set(&lock->val, LOCK_UNLOCKED);
     61        atomic_set(&lock->cnt, 0);
    5762#ifdef CONFIG_DEBUG_SPINLOCK
     63        lock->magic1 = LOCK_MAGIC1;
     64        lock->magic2 = LOCK_MAGIC2;
    5865        lock->name = name;
    5966#endif
    6067}
    6168
    6269#ifdef CONFIG_DEBUG_SPINLOCK
    6370
     71static const char *le_str[] = {
     72        "invalid",
     73        "spinlock_lock",
     74        "spinlock_trylock",
     75        "spinlock_unlock"
     76};
     77
     78typedef enum {
     79        LE_INVALID = 0,
     80        LE_LOCK,
     81        LE_TRYLOCK,
     82        LE_UNLOCK
     83} lock_event_type_t;
     84
     85typedef struct {
     86        lock_event_type_t type;
     87        spinlock_t *lock;
     88        cpu_t *cpu;
     89        thread_t *thread;
     90        unative_t pc;
     91        uint64_t cycle;
     92        atomic_count_t cnt;
     93} lock_event_t;
     94
     95#define LE_EVENTS       8000
     96
     97static lock_event_t lock_events[LE_EVENTS];
     98static atomic_t ne;
     99
     100static int lock_tracing = 1;
     101
     102void lock_event_record(lock_event_type_t type, spinlock_t *l, unative_t pc);
     103void lock_event_record(lock_event_type_t type, spinlock_t *l, unative_t pc)
     104{
     105        if (!lock_tracing)
     106                return;
     107        if (l->name[0] == '*')
     108                return;
     109
     110        int i = atomic_postinc(&ne) % LE_EVENTS;
     111
     112        lock_events[i].type = type;
     113        lock_events[i].lock = l;
     114        lock_events[i].cpu = CPU;
     115        lock_events[i].thread = THREAD;
     116        lock_events[i].pc = pc;
     117        lock_events[i].cycle = get_cycle();
     118        lock_events[i].cnt = atomic_get(&l->cnt);
     119}
     120
     121void lock_event_print(lock_event_t *le);
     122void lock_event_print(lock_event_t *le)
     123{
     124
     125        printf("cycle=%p ", le->cycle);
     126        if (le->type > LE_UNLOCK)
     127                le->type = 0;
     128        printf("%s(%s/%p) ", le_str[le->type], le->lock->name, le->lock);
     129        if (le->cpu)
     130                printf("cpu%d, ", le->cpu->id);
     131        else
     132                printf("nocpu, ");
     133        printf("pc=%p ", le->pc);
     134        printf("cnt=%ld ", le->cnt);
     135        printf("thread=%p\n", le->thread);
     136}
     137
     138void lock_event_show(spinlock_t *l);
     139void lock_event_show(spinlock_t *l)
     140{
     141        int i, j = 0;
     142        uint64_t min = 0xffffffffffffffffULL;
     143
     144        for (i = 0; i < LE_EVENTS; i++) {
     145                if (lock_events[i].cycle < min) {
     146                        min = lock_events[i].cycle;
     147                        j = i;
     148                }
     149        }
     150
     151        for (i = j; i < LE_EVENTS + j; i++) {
     152                lock_event_t *e = &lock_events[i % LE_EVENTS];
     153               
     154                if (e->lock == l)
     155                        lock_event_print(e);
     156        }
     157}
     158
    64159/** Lock spinlock
    65160 *
    66161 * Lock spinlock.
     
    75170        size_t i = 0;
    76171        bool deadlock_reported = false;
    77172       
     173        ASSERT(lock->magic1 == LOCK_MAGIC1);
     174        ASSERT(lock->magic2 == LOCK_MAGIC2);
     175
    78176        preemption_disable();
    79         while (test_and_set(&lock->val)) {
     177        while (test_and_set(&lock->val) != LOCK_UNLOCKED) {
    80178                /*
    81179                 * We need to be careful about particular locks
    82180                 * which are directly used to report deadlocks
     
    110208                }
    111209        }
    112210       
     211        atomic_inc(&lock->cnt);
     212        if (atomic_get(&lock->cnt) != 1) {
     213                lock_tracing = 0;
     214                lock_event_show(lock);
     215                panic("not alone in critical section");
     216        }
     217
    113218        if (deadlock_reported)
    114219                printf("cpu%u: not deadlocked\n", CPU->id);
    115220       
     221
     222        lock_event_record(LE_LOCK, lock, CALLER);
     223       
    116224        /*
    117225         * Prevent critical section code from bleeding out this way up.
    118226         */
    119227        CS_ENTER_BARRIER();
     228        if (atomic_get(&lock->cnt) != 1) {
     229                lock_tracing = 0;
     230                lock_event_show(lock);
     231                panic("not alone in critical section");
     232        }
    120233}
    121234
    122235#endif
     
    135248int spinlock_trylock(spinlock_t *lock)
    136249{
    137250        preemption_disable();
    138         int rc = !test_and_set(&lock->val);
     251        atomic_count_t ret = test_and_set(&lock->val);
     252
     253        ASSERT(lock->magic1 == LOCK_MAGIC1);
     254        ASSERT(lock->magic2 == LOCK_MAGIC2);
     255        ASSERT(ret == LOCK_LOCKED || ret == LOCK_UNLOCKED);
    139256       
    140257        /*
    141258         * Prevent critical section code from bleeding out this way up.
    142259         */
    143260        CS_ENTER_BARRIER();
    144261       
    145         if (!rc)
     262        if (ret == LOCK_LOCKED)
    146263                preemption_enable();
    147        
    148         return rc;
    149 }
    150 
     264        else {
     265                if (atomic_postinc(&lock->cnt) != 0)
     266                        panic("This lock is locked!");
     267                lock_event_record(LE_TRYLOCK, lock, CALLER);
     268        }
     269       
     270        return ret == LOCK_UNLOCKED;
     271}
     272
     273void spinlock_unlock(spinlock_t *lock)
     274{
     275        ASSERT(lock->magic1 == LOCK_MAGIC1);
     276        ASSERT(lock->magic2 == LOCK_MAGIC2);
     277
     278        lock_event_record(LE_UNLOCK, lock, CALLER);
     279        if (atomic_get(&lock->val) != LOCK_LOCKED) {
     280                lock_tracing = 0;
     281                lock_event_show(lock);
     282                panic("unlocking non-locked lock");
     283        }
     284       
     285        /*
     286         * Prevent critical section code from bleeding out this way down.
     287         */
     288        CS_LEAVE_BARRIER();
     289       
     290        atomic_dec(&lock->cnt);
     291        atomic_set(&lock->val, LOCK_UNLOCKED);
     292        preemption_enable();
     293}
    151294#endif
    152295
    153296/** @}