aboutsummaryrefslogtreecommitdiffstats
path: root/manual/CHAPTER_Auxlibs.tex
blob: 8d3ed743030c115800239a6d02889c7c07ad66f9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
\chapter{Auxilary Libraries}

The Yosys source distribution contains some auxilary libraries that are bundled
with Yosys.

\section{SHA1}

The files in {\tt libs/sha1/} provide a public domain SHA1 implementation written
by Steve Reid, Bruce Guenter, and Volker Grabsch. It is used for generating
unique names when specializing parameterized modules.

\section{BigInt}

The files in {\tt libs/bigint/} provide a library for performing arithmetic with
arbitrary length integers. It is written by Matt McCutchen \citeweblink{bigint}.

The BigInt library is used for evaluating constant expressions, e.g.~using the {\tt
ConstEval} class provided in {\tt kernel/consteval.h}.

\section{SubCircuit}
\label{sec:SubCircuit}

The files in {\tt libs/subcircuit} provide a library for solving the subcircuit
isomorphism problem. It is written by Clifford Wolf and based on the Ullmann
Subgraph Isomorphism Algorithm \cite{UllmannSubgraphIsomorphism}. It is used by
the {\tt extract} pass (see {\tt help extract} or Sec.~\ref{cmd:extract}).

\section{ezSAT}

The files in {\tt libs/ezsat} provide a library for simplifying generating CNF
formulas for SAT solvers. It also contains bindings of MiniSAT. The ezSAT
library is written by Clifford Wolf. It is used by the {\tt sat} pass (see
{\tt help sat} or Sec.~\ref{cmd:sat}).
800; font-weight: bold } /* Keyword */ .highlight .ch { color: #888888 } /* Comment.Hashbang */ .highlight .cm { color: #888888 } /* Comment.Multiline */ .highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */ .highlight .cpf { color: #888888 } /* Comment.PreprocFile */ .highlight .c1 { color: #888888 } /* Comment.Single */ .highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */ .highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .gr { color: #aa0000 } /* Generic.Error */ .highlight .gh { color: #333333 } /* Generic.Heading */ .highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ .highlight .go { color: #888888 } /* Generic.Output */ .highlight .gp { color: #555555 } /* Generic.Prompt */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #666666 } /* Generic.Subheading */ .highlight .gt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
/******************************************************************************
 * tasklet.c
 * 
 * Tasklets are dynamically-allocatable tasks run in either VCPU context
 * (specifically, the idle VCPU's context) or in softirq context, on at most
 * one CPU at a time. Softirq versus VCPU context execution is specified
 * during per-tasklet initialisation.
 * 
 * Copyright (c) 2010, Citrix Systems, Inc.
 * Copyright (c) 1992, Linus Torvalds
 * 
 * Authors:
 *    Keir Fraser <keir@xen.org>
 */

#include <xen/config.h>
#include <xen/init.h>
#include <xen/sched.h>
#include <xen/softirq.h>
#include <xen/tasklet.h>
#include <xen/cpu.h>

/* Some subsystems call into us before we are initialised. We ignore them. */
static bool_t tasklets_initialised;

DEFINE_PER_CPU(unsigned long, tasklet_work_to_do);

static DEFINE_PER_CPU(struct list_head, tasklet_list);
static DEFINE_PER_CPU(struct list_head, softirq_tasklet_list);

/* Protects all lists and tasklet structures. */
static DEFINE_SPINLOCK(tasklet_lock);

static void tasklet_enqueue(struct tasklet *t)
{
    unsigned int cpu = t->scheduled_on;

    if ( t->is_softirq )
    {
        struct list_head *list = &per_cpu(softirq_tasklet_list, cpu);
        bool_t was_empty = list_empty(list);
        list_add_tail(&t->list, list);
        if ( was_empty )
            cpu_raise_softirq(cpu, TASKLET_SOFTIRQ);
    }
    else
    {
        unsigned long *work_to_do = &per_cpu(tasklet_work_to_do, cpu);
        list_add_tail(&t->list, &per_cpu(tasklet_list, cpu));
        if ( !test_and_set_bit(_TASKLET_enqueued, work_to_do) )
            cpu_raise_softirq(cpu, SCHEDULE_SOFTIRQ);
    }
}

void tasklet_schedule_on_cpu(struct tasklet *t, unsigned int cpu)
{
    unsigned long flags;

    spin_lock_irqsave(&tasklet_lock, flags);

    if ( tasklets_initialised && !t->is_dead )
    {
        t->scheduled_on = cpu;
        if ( !t->is_running )
        {
            list_del(&t->list);
            tasklet_enqueue(t);
        }
    }

    spin_unlock_irqrestore(&tasklet_lock, flags);
}

void tasklet_schedule(struct tasklet *t)
{
    tasklet_schedule_on_cpu(t, smp_processor_id());
}

static void do_tasklet_work(unsigned int cpu, struct list_head *list)
{
    struct tasklet *t;

    if ( unlikely(list_empty(list) || cpu_is_offline(cpu)) )
        return;

    t = list_entry(list->next, struct tasklet, list);
    list_del_init(&t->list);

    BUG_ON(t->is_dead || t->is_running || (t->scheduled_on != cpu));
    t->scheduled_on = -1;
    t->is_running = 1;

    spin_unlock_irq(&tasklet_lock);
    sync_local_execstate();
    t->func(t->data);
    spin_lock_irq(&tasklet_lock);

    t->is_running = 0;

    if ( t->scheduled_on >= 0 )
    {
        BUG_ON(t->is_dead || !list_empty(&t->list));
        tasklet_enqueue(t);
    }
}

/* VCPU context work */
void do_tasklet(void)
{
    unsigned int cpu = smp_processor_id();
    unsigned long *work_to_do = &per_cpu(tasklet_work_to_do, cpu);
    struct list_head *list = &per_cpu(tasklet_list, cpu);

    /*
     * Work must be enqueued *and* scheduled. Otherwise there is no work to
     * do, and/or scheduler needs to run to update idle vcpu priority.
     */
    if ( likely(*work_to_do != (TASKLET_enqueued|TASKLET_scheduled)) )
        return;

    spin_lock_irq(&tasklet_lock);

    do_tasklet_work(cpu, list);

    if ( list_empty(list) )
    {
        clear_bit(_TASKLET_enqueued, work_to_do);        
        raise_softirq(SCHEDULE_SOFTIRQ);
    }

    spin_unlock_irq(&tasklet_lock);
}

/* Softirq context work */
static void tasklet_softirq_action(void)
{
    unsigned int cpu = smp_processor_id();
    struct list_head *list = &per_cpu(softirq_tasklet_list, cpu);

    spin_lock_irq(&tasklet_lock);

    do_tasklet_work(cpu, list);

    if ( !list_empty(list) && !cpu_is_offline(cpu) )
        raise_softirq(TASKLET_SOFTIRQ);

    spin_unlock_irq(&tasklet_lock);
}

void tasklet_kill(struct tasklet *t)
{
    unsigned long flags;

    spin_lock_irqsave(&tasklet_lock, flags);

    if ( !list_empty(&t->list) )
    {
        BUG_ON(t->is_dead || t->is_running || (t->scheduled_on < 0));
        list_del_init(&t->list);
    }

    t->scheduled_on = -1;
    t->is_dead = 1;

    while ( t->is_running )
    {
        spin_unlock_irqrestore(&tasklet_lock, flags);
        cpu_relax();
        spin_lock_irqsave(&tasklet_lock, flags);
    }

    spin_unlock_irqrestore(&tasklet_lock, flags);
}

static void migrate_tasklets_from_cpu(unsigned int cpu, struct list_head *list)
{
    unsigned long flags;
    struct tasklet *t;

    spin_lock_irqsave(&tasklet_lock, flags);

    while ( !list_empty(list) )
    {
        t = list_entry(list->next, struct tasklet, list);
        BUG_ON(t->scheduled_on != cpu);
        t->scheduled_on = smp_processor_id();
        list_del(&t->list);
        tasklet_enqueue(t);
    }

    spin_unlock_irqrestore(&tasklet_lock, flags);
}

void tasklet_init(
    struct tasklet *t, void (*func)(unsigned long), unsigned long data)
{
    memset(t, 0, sizeof(*t));
    INIT_LIST_HEAD(&t->list);
    t->scheduled_on = -1;
    t->func = func;
    t->data = data;
}

void softirq_tasklet_init(
    struct tasklet *t, void (*func)(unsigned long), unsigned long data)
{
    tasklet_init(t, func, data);
    t->is_softirq = 1;
}

static int cpu_callback(
    struct notifier_block *nfb, unsigned long action, void *hcpu)
{
    unsigned int cpu = (unsigned long)hcpu;

    switch ( action )
    {
    case CPU_UP_PREPARE:
        INIT_LIST_HEAD(&per_cpu(tasklet_list, cpu));
        INIT_LIST_HEAD(&per_cpu(softirq_tasklet_list, cpu));
        break;
    case CPU_UP_CANCELED:
    case CPU_DEAD:
        migrate_tasklets_from_cpu(cpu, &per_cpu(tasklet_list, cpu));
        migrate_tasklets_from_cpu(cpu, &per_cpu(softirq_tasklet_list, cpu));
        break;
    default:
        break;
    }

    return NOTIFY_DONE;
}

static struct notifier_block cpu_nfb = {
    .notifier_call = cpu_callback,
    .priority = 99
};

void __init tasklet_subsys_init(void)
{
    void *hcpu = (void *)(long)smp_processor_id();
    cpu_callback(&cpu_nfb, CPU_UP_PREPARE, hcpu);
    register_cpu_notifier(&cpu_nfb);
    open_softirq(TASKLET_SOFTIRQ, tasklet_softirq_action);
    tasklets_initialised = 1;
}

/*
 * Local variables:
 * mode: C
 * c-file-style: "BSD"
 * c-basic-offset: 4
 * tab-width: 4
 * indent-tabs-mode: nil
 * End:
 */