OS 2012

General

Useful code snippets

#include <unistd.h>
#include <stdio.h>

int main() {
    int pid=0;
    int status;
    int fds[2];
    pipe(fds);
    if (pid=fork()) {
        // parent
        dup2(fds[1], 1);
        close(fds[0]);
        close(fds[1]);
        execl ("/bin/ls", "ls", NULL);
    }
    else {
        // child
        dup2(fds[0], 0);
        close(fds[0]);
        close(fds[1]);
        execl ("/bin/grep", "grep", "c", NULL);
    }
}
#include <unistd.h>
#include <stdio.h>

int main() {
    int status;

    int pgp=fork();
    if (pgp == 0)
    {
        setpgid(0, 0);

        int fds[2];
        pipe(fds);
        int lspid=fork();
        if (lspid == 0) {
            dup2(fds[1], 1);
            close(fds[0]);
            close(fds[1]);
            sleep(100);
            execl("/bin/ls", "ls", NULL);
            _exit(255);
        }
        dup2(fds[0], 0);
        close(fds[0]);
        close(fds[1]);
        sleep(100);
        execl ("/bin/grep", "grep", "c", NULL);
        _exit(255);
    }
    setpgid(pgp, pgp);
    waitpid(pgp, &status, 0);
    return 0;
}
#include <unistd.h>
#include <stdio.h>

int main() {
        close(0);
        close(1);
        close(2);
        if (!fork())
        {
            setsid();
            sleep(100);
        }
    return 0;
}
#include <unistd.h>
#include <stdio.h>
#include <signal.h>

int pgp = 0;
int lspid = 0;

void interrupt_handler(int foo) {
    if (pgp)
        kill(-pgp, SIGINT);
}

int main() {
    int status;
    signal(SIGINT, &interrupt_handler); // This is cruel
                                        // use sigaction(2)

    pgp=fork();
    if (pgp == 0)
    {
        setpgid(0, 0);

        int fds[2];
        pipe(fds);
        lspid=fork();
        if (lspid == 0) {
            dup2(fds[1], 1);
            close(fds[0]);
            close(fds[1]);
            sleep(100);
            execl("/bin/ls", "ls", NULL);
            _exit(255);
        }
        dup2(fds[0], 0);
        close(fds[0]);
        close(fds[1]);
        sleep(100);
        execl ("/bin/grep", "grep", "c", NULL);
        _exit(255);
    }
    setpgid(pgp, pgp);
    waitpid(pgp, &status, 0);
    return 0;
}

Homework 2

Требуется реализовать аналог утилиты find, поддерживающий опции -type и -iname, при помощи рекурсивного обхода на чистом bash с использованием только встроенных команд и, может быть, утилиты grep. Следовать симлинкам не следует.

#!/bin/bash

testwith() {
find           testdir -type $1 -iname "$2" | sort > /tmp/hw2-result.orig
./bash/find.sh testdir -type $1 -iname "$2" | sort > /tmp/hw2-result.gens
if diff /tmp/hw2-result.orig /tmp/hw2-result.gens &> /dev/null ;
then
  echo OK
else
  echo "FAIL: $1 '$2'"
fi
rm /tmp/hw2-result.*
}

for t in d f ;
do
  for iname in '*' '*.txt' 'txt.*' ;
  do
    testwith $t "$iname"
  done
done

В тестере могут быть баги, я его не запускал. Приведённый тестер “хорошо” работает только, если его запускают на “своей” машине. В противном случае рекомендуется прочитать man по mktemp(1).

Класть тестер и тестовую директорию в основной бранч репозитория не следует.

Homework 3

Требуется реализовать скрипт, представляющий собой мутабельную очередь для утилиты wget. Аргументами скрипта являются URLы. При запуске первый инстанс должен демонизироваться, а остальные запуски только добавлять этому демону задания в очередь.

#!/bin/bash

shopt -s nullglob

QPATH=$HOME/.nyaqueue

mkdir -p "$QPATH"
mkdir -p "$QPATH/requests"

for a in "$@"
do
    r=`mktemp --tmpdir="$QPATH/requests"`
    echo "$a" > "$r"
done

if [[ ! -f "$QPATH/running" ]]; then
    touch "$QPATH/running"
    trap "rm '$QPATH/running'" 0

    while [ 1 ]
    do
        for a in "$QPATH/requests"/*
        do
            url=`cat "$a"`
            rm "$a"
            wget -c "$url"
        done

        sleep 1
    done
fi

Комментарии

По поводу демонизации в bash. В задании требуется:

Для выполнения последнего следует разобраться, что означает конструкция

exec > /dev/null

Также следует ответить себе на вопрос “Почему в bash нельзя без trap?”

Midterm #1

Требуется поговорить со мной, что-то написать, получить от 0 до 50 баллов.

Homework 4

Требуется реализовать мега-урезанную версию утилиты sed.

Часть первая

Требуется реализовать библиотеку для построчного чтения из файлового дескриптора при помощи лишь одного системного вызова read со следующим интерфесом:

// Структура, в которой прячется файловый дескриптор, буфер и хозяйственная
// информация.
struct RL;

// Принимает файловый дескриптор и максимальный размер строки, которую требуется
// обрабатывать и возвращает указатель на свежевыделенную структуру типа RL
// или NULL в случае ошибки.
RL* rl_open(int fd, size_t max_size);

// Возвращает max_size, указанный при создании rl.
size_t rl_max_size (RL *rl);

// Освобождает структуру rl. При этом следует закрыть и файловый дескриптор,
// спрятанный внутри. Возвращает $0$, если всё хорошо или $-1$ в случае ошибки.
// В последнем случае код ошибки должен возвращаться через errno.
int rl_close(RL *rl);

// Читает строку (включая символ перевода строки) размером не более
// $min(max_size + 1, buf_size)$ из файлового дескриптора спрятанного
// в rl в буфер buf.
// * В случае успеха записывает строку в buf (включая перевод строки) и возвращает
// длину записанных в buf данных. Частичный результат не допускается.
// * В случае конца ввода возвращает $0$.
// * В случае, если строка в файловом дескрипторе больше `max_size + 1`
// возвращает $-3$. Несколько последующих вызовов также могут возвращать $-3$
// (пропуск хвоста слишком длинной строки).
// * В случае, если длина строки на вводе меньше `max_size + 1`, но больше
`buf_size`, то возвращает $-2$. Строка при этом безвозвратно выбрасывается.
// * В остальных случаях возвращает $-1$, устанавливая errno в код произошедшей
// ошибки.
// Философские факты: бывают строки нулевой длины, все строки файла кроме
// последней всегда заканчиваются `\n`, последняя строка в файле никогда не
// заканчивается `\n`.
int rl_readline(RL *rl, char * buf, size_t buf_size);

Часть вторая

На любом языке программирования реализовать тестер своей программы. Должен работать следующим образом:

123\n12
пауза в 5 секунд
345\n

вывод (для достаточно большого n) должен быть:

123\n
пауза в 5 секунд
12345\n

а не

пауза в 5 секунд
123\n12345\n

Часть третья

Превратите readlines в shared-библиотеку. В Makefile следует добавить цель all-shared, собирающую библиотеку и readlines-main.c в бинарник динамический слинкованный с ней.

Часть четвёртая

Наконец, реализуйте урезанную версию утилиты sed. Требуется уметь поддерживать только команду s без флагов и с флагом g. Сохранение синтаксиса sed для групп в регулярных выражения необязательно.

Для работы с регулярными выражениями следует использовать библиотеку pcre, динамически линкуясь с ней (во всех целях сборки).

«Программа» (sed-скрипт) передаётся в качестве единственного аргумента unsed, ввод читается со stdin. Следует считать, что на ввод подаётся строка в UTF-8.

Пример запуска (синтаксис для групп может отличаться):

cat file | ./unsed 's/123/321/g
                    s%\([^s]*\)sss%haha\1rrr%'

Midterm #2

Требуется поговорить со мной, что-то написать, получить от 0 до 50 баллов.

Homework 5

Требуется реализовать вариант аллокатора Хоарда с тремя субаллокаторами:

Для начала можно считать, что k = 32, K = 64K, но это должно быть можно просто поменять. Настоятельно советую потестить то, что получается при разных параметрах.

Homework 6

Требуется реализовать утилиту, принимающую 2 * n номеров файловых дескрипторов в argv и копирующую данные из дескриптора 2 * k - 1 в 2 * k для всех k, 1 <= k <= n с использованием poll(2) и epoll(2).

/copy-paster/tester.sh должен принимать имя бинарника в качестве аргумента и тестировать его на профпригодность. В случае, если что-то не так, tester.sh должен завершаться с ненулевым кодом возврата. Внутри у tester.sh и (если есть) tester.c должно происходить что-то разумное, а не создание видимости тестирования. В частности, следует проверить что произойдёт в случае, если пишущий конец какого-то fd закроется потому, что пишущий процесс погиб.