Я наконец-то избавился от использования POP3 для получения электронной почты. Все и так работало и как-то не хотелось менять.
Но так как приходится использовать несколько десктопов, то POP3 уже не годится.

Из обнаруженного интересного:
1) в Evolution есть встроенный бэкап и восстановление почты (но работает достаточно долго; видимо, из-за использования xz для сжатия)
2) IMAP в gmail имеет какие-то свои особенности, но, в целом, работает
3) Настраивается подключение в Evolution на удивление легко
4) Evolution для аутентификации в gmail умеет использовать OAuth2 (в дополнение к более традиционным методам). Не знаю, хорошо ли это или плохо.
Доклад с “Curiously Recurring C++ Bugs at Facebook” от Louis Brandy с CppCon 2017 показывает несколько примеров, почему местам Rust лучше, чем C++.

https://www.youtube.com/watch?v=lkgszkPnV8g

Не могу не сослаться на то, что ICFPC будет 13 июля.

Что-то много очень адептов node.js и прочих «магических» технологий говорят о том, что «нити (threads) и блокирующие вызовы - suxx», а «лапша из колбэков и асинхронные вызовы - rulezzz».

TL;DR

  1. event-driven concurrency с колбэками эквивалентно thread-based concurrency
  2. можно реализовать нити (threads) с минимальным оверхедом
  3. нити дают возможность писать естественный, последовательный код
  4. поэтому threads >> events + callbacks

Немного теории.

И последовательный блокирующийся процесс вычисления, и асинхронный неблокирующийся процесс имеют определенное состояние. Например, для процесса обработки http-запроса состояние может содержать:

  • сокет и связанные с ним ресурса ядра
  • буфер для чтения из сокета в юзерспейсе
  • состояние http-парсера
  • заголовки http и тело запроса
  • состояние парсера тела запроса
  • буфер для ответа
  • внутренние данные функции, генерирующей ответ на запрос (например, буфер под результат запроса к БД)

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

Пропоненты некоторых модных технологий убедительно рассказывают о том, что единственный правильный способ написания «web-scale»-приложений - это отказ от нитей и блокирующихся вызовов и переход на написание программ в стиле «лапша из колбэков». «Лапша из колбэков» есть ни что иное, как код в continuation-passing style. Осуществить преобразование последовательного кода в CPS вручную - задача довольно механическая, трудоемкая и склонная к ошибкам.

К сожалению, сложилась ситуация, когда многие программисты не имеют базового образования в области Computer Science и имеют слабое представление о процессах вычисления (в отличие, например, от выпускников университетов, где преподают курсы вроде SICP). На самом же деле, CPS и последовательный код эквивалентны друг другу: цепочка колбэков - это стек вызовов, представленный в виде односвязного списка.

Основной мой аргмент за последовательный код, выполняющийся в отдельных нитях, следующий: последовательный код легко читается, структуры управления в нем реализуются легко. Такой код надежнее, так как есть простые и надежные инструменты для обработки ошибок; есть исключения; стектрейсы содержат полезную информацию; легче следить за своевременным освобождением ресурсов.

Практика.

Основной аргумент, высказываемый против thread-based concurrency - это то, что нити занимают много ресурсов и поэтому их нельзя много создать. Для нативных нитей это так и есть: у них есть относительно большой оверхед на создание, значительно потребление памяти (место тратится под стэк (обычно несколько мегабайтов), thread-local storage, информация для планировщике нитей в ядре) и значительный оверхед на переключение контекста. Но нити, предоставленные ОС - это только один из вариантов реализации нитей: их можно реализовать с меньшим оверхедом.

Разберем, например, нити в Linux + glibc. Итак, что включает в себя нить:

  • структуры данных в ядре ОС, которые содержат информацию для планировщика
  • стэк
  • сохраненные значения регистров CPU и FPU
  • маска сигналов нити
  • место под результат нити
  • объекты синхронизации

Основные накладные расходы при использовании таких нитей заключается в следующем:

  • переключение нитей всегда происходит из ядра ОС, т.е. всегда есть переход в userspace и обратно; а это губительно для производительности, если происходит много переключений
  • планировщик нитей, в зависимости от реализации, может начать тормозить из-за большого количества нитей
  • обычно у нитей достаточно большой стек, около нескольких Мб; из-за этого они занимают много памяти. Это основная причина, почему нельзя создать много нативных нитей

Первое, на что можно обратить внимание, это наличие в POSIX средств для переключения контекста - makecontext, getcontext, setcontext, swapcontext. Контекст в POSIX представляет собой все состояние нити за исключением объектов ядра и объектов синхронизации. С помощью таких контекстов можно довольно просто организовать нити. Такие нити, созданные в userspace, называются green threads. При этом, стэк для нити мы должны предоставить сами; это дает возможность управлять и минимизировать потребление памяти нитями.

Самый большой минус контекстов POSIX заключается в том, что контекст хранит также маску сигналов, и для ее переключения нужен системный вызов (чтобы обеспечить POSIX'ную семантику переключения контекста). Причем зачастую маска сигналов на самом деле и не нужна. Если реализовать swapcontext вручную (это займет несколько десяток строк кода на ассемблере для каждой поддерживаемой архитектуры), то накладные расходы сильно уменьшатся. Также можно не сохранять те регистры, которые не обязаны быть сохранены при вызове функции.

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

В итоге, использование green threads позволяет писать такой же простой последовательный код и запускать много нитей. Поэтому я выбираю green threads для задач, связанных с I/O; а для остальных задач - OS threads.

See also:

PS[0]. А node.js вместе при использовании node-fibers совсем даже неплох (если закрыть глаза и не видеть javascript). node-fibers использует libcoroutine для организации легковесных нитей в v8, что спасает от лапши из колбэков.

PS[1]. Erlang с его сотнями тысяч процессов - типичный пример успешного использования green threads.

Job ad

Jan. 16th, 2012 04:13 pm

Казанской компании 10tracks, в которой я сейчас работаю, нужны программисты:

  • javascript-программист для браузерного фронтенда
  • программист мобильных приложений
  • программист бэкенда (сейчас бэкенд на java, но все может поменяться)

Возможны различные варианты устройства (в том числе и студентам на part-time).

Подробности вакансий — в http://10tracks.ru/job/.

Также вопросы можно задавать мне в личную почту.

Я уже некоторое значительное время не пишу ничего на лиспе, и поэтому мои лисповые проекты остаются заброшенными. Среди них есть и cl-gtk2. Но я не хочу, чтобы cl-gtk2 перестал развиваться, т.к. думаю, что он полезен и нужен для лисп-сообщества.

Поэтому я ищу желающих взять на себя cl-gtk2. Со своей стороны обещаю всяческую поддержку в виде консультаций и помощи.

Смержил патч от akovalenko, использующий TLS-слот 63. С ним и возникла проблема — каким-то образом забыл смержить следующий его коммит, исправляющий опечатку; из-за этого (и из-за нехватки времени) не мог понять, в чем дело. Вообще, надо быть внимательнее и не допускать таких оплошностей.

После чего уже смержил SBCL-1.0.45 и выложил сборку (содержащую часть патчей от akovalenko) на https://sites.google.com/site/dmitryvksite/sbcl-distr/sbcl-1.0.45-threads.msi.

update

Dec. 17th, 2010 12:02 am

Опять вынужден заниматься отладкой SBCL - после мержа версии sbcl и akovalenko в sbcl-windows-threads стали появляться странные ошибки доступа к памяти. Но после разборок с ними надо будет заканчивать с нитями и отправлять в SBCL.

Apache Harmony JVM под виндой также использует поле Arbitrary Data в TIB для хранения указателя на TLS (пруфлинк).

А еще это поле используется для хранения TLS в библиотеке GML (OpenGL Multithreading Library) внутри проекта Spring (Spring - это игровой движок для запуска игр вроде Total Annihilation).

Встретил в блог-посте ссылку на статью «One-pass Code Generation in V8» (хотя это скорее набор слайдов к докладу, но буду так называть). Статья мне очень понравилась, как по содержанию, так и по стилю подачи материала. В ней описывается архитектура кодогенератора, которая содержит несколько техник, которые позволяют генерировать код без «глупостей» вроде "push eax; pop eax;" без применения peephole-оптимизатора, а за счет предоставления большей информации для процедур генерации примитивных операций.

На первый взгляд, довольно похоже на архитектуру кодогенерации в SBCL.

Изучать что-то по подобным статьям - одно удовольствие.

Выложил новую версию cl-sqlite-0.2.

Добавилась поддержка именованных параметров в запросах. Для сигнализирования ошибок используется тип sqlite-error вместо cl:error.

Ссылка на скачивание: http://common-lisp.net/project/cl-sqlite/releases/cl-sqlite-0.2.tar.gz.

Обновил sbcl-windows-threads до SBCL-1.0.44, инсталлятор выложил на https://sites.google.com/site/dmitryvksite/sbcl-distr/sbcl-1.0.44-threads-1.msi.

The updated version of implementation notes is published on http://dmitryvk.github.com/sbcl-win32-threads/implementation-notes.html

Suspend

Thread suspension is implemented as safepoints. Safepoint is implemented with read of memory location ('GC poll address' which is located in 'GC poll page').

At first phase, the 'master' thread unmaps the GC poll page. After this, other threads will at some time get page faults. There are several issues that must be dealt with:

1) The reaction to unmapping is not immediate - thread must reach the safepoint

2) Some threads will not reach safepoint soon (if thread is executing foreign code or a blocking system call)

3) Even if a thread has reached a safepoint, it does not mean that GC can start. The thread may be inside WITHOUT-GCING section, for example. In this case, thread may not be resumed with GC poll page unmapped.

We can draw some conclusions:

1) Every thread that can reach safepoint (if it's not in foreign code or in blocking syscall) must reach it before GC can proceed.

1.a) Every thread can can not reach safepoint must not interfere with GC if it will suddenly return to lisp code

2) After all threads have reached safepoint, we must wait for all threads to be ready for GC.

This implies two-phase suspend.

Phase 1:

1) GC poll page is remapped as unreadable

2) master thread checks each thread: if it's running lisp code, wait until it reaches a safepoint. Thread is considered to reach a safepoint when it's state is STATE_SUSPENDED_BRIEFLY.

Phase 2:

1) GC poll page is mapped again so that threads can run until they are ready for gc

2) Master thread waits for every thread to be ready for GC. This is achieved by waiting for state of every thread to become STATE_SUSPENDED (except for threads that are ready for GC)

Thread is ready for GC if:

1) thread_state(thread) == STATE_SUSPENDED

2) thread_is running foreign code and it is not inside WITHOUT-GCING or WITHOUT-INTERRUPTS and blockable signals are unblocked

For this, thread-local variable *GC-SAFE* is introduced - it tracks the current readiness for GC of a thread. It is guaranteed that when *GC-SAFE* changes from NIL to T, thread checks if GC is in progress and enters suspended state.

Thread interruption is similar, but we don't need to wait for all threads to reach a safepoint - it is only necessary for interrupted thread to reach safepoint.

Phase 1:

1) GC poll page is remapped as unreadable

2) master thread checks interrupted thread: if it's running lisp code, wait until it reaches a safepoint. Thread is considered to reach a safepoint when it's state is STATE_SUSPENDED_BRIEFLY.

Phase 2:

1) GC poll page is mapped

2) All threads that have reached a safepoint are released

Safepoint code

Safepoint code is called to check whether thread has something to do related to SBCL internal working. It is called:

1) When thread reaches a safepoint and GC poll page is unmapped

2) When leaving and entering foreign code

3) At other occasions.

Safepoints have several responsibilities.

1) If there is a GC or thread interruption in progress, thread has to notify the master thread that it is has reached a safepoint. Safepoint does this by changing the state to STATE_SUSPENDED_BRIEFLY and waiting for state to be changed by master thread. When it resumes, thread checks whether it should suspend or interrupt.

2) If thread should suspend, it is checked whether thread can suspend. If thread is suspendable, it changes its state to STATE_SUSPENDED; otherwise, it sets STOP_FOR_GC_PENDING (and sets pseudo_atomic_interrupted)

3) If thread should interrupt, it either sets INTERRUPT_PENDING and pseudo_atomic_interrupted or executes interruption.

4) If GC is pending and thread can do GC, runs the GC

5) Is interrupt is pending and thread can execute it, executes it.

On some occasions, runtime is in very fragile state and can not really do anything that safepoint must do (e.g., change thread state, execute GC, execute interruption). Thses are e.g. using lisp thread synchronization primitives. To control this, *DISABLE-SAFEPOINTS* variable is used.

GC code is run inside a safepoint, and safepoint code is not reenterable. GC code itself has safepoints (since SUB-GC is a normal lisp function, it calls lisp synchronization routines and does several switches to/from foreign code). To prevent rentering of a safepoint code, *IN-SAFEPOINT* variable is used.

Купил недавно мышку беспроводную от Logitech. В мануале написано:

«Горизонтальная прокрутка (функция может меняться в зависимости от программного приложения). Эта функция не работает в Linux.»

И вот с чего бы им так нагло врать?

The updated version of implementation notes is published on http://dmitryvk.github.com/sbcl-win32-threads/implementation-notes.html

Since I've asked for a review of Windows threads patches for SBCL, I'm publishing my implementation notes.

Thread-local storage

For each thread Windows allocates a Thread Information Block[1,2,3]. Thread can access its own Thread Information Block through FS register (e.g., %fs:0 is a first field in TIB). TIB contains frequently used thread-specific data such as Last Error Number, pointer to SEH (structured exception handling) frame, thread id, TLS backing store. This structure is documented in [2] and [4]. TIB has an 'Arbitrary' field which is described as:

The 14h DWORD pvArbitrary field is theoretically available for applications to use however they want. It's almost like an extra thread local storage slot for you to use, although I've never seen an application use it.

This sound just like what is needed for implementing thread-local storage - a memory location that we can freely use and that is easily accessible. Unfortunately, there is a possibility that some library would also use this field for own purposes (and there are examples of such libraries). And when come other conflicting code will run, it will be hard to detect this.

So clearly, a better way of storing TLS pointer is needed. TIB also contains first 64 slots for Windows' thread-local storage. There are several options of how to implement TLS with that:

  1. Windows allows executables to preallocate TLS slots. We can take, e.g., TLS slot 0 and all access to lisp's TLS will go through TLS at fixed offset. But it would somewhat complicate the initialization of lisp runtime and the build process.
  2. We can grab some other fixed slot number by successively allocating TLS slots (TlsAlloc) until we get the slot we want. After that, we free the slots we allocated that we don't need. This way, we can use TLS slot 63 and lisp's TLS pointer will be at a known offset. It is quite safe to use this slot; libraries on Windows commonly use no more that one TLS slot (and 'system' libraries don't even use TLS — they have their own fields in TIB).
  3. We can allocate the TLS slot in normal Windows way and store it in a global variable. This way, we don't need to any strange things, but TLS access will have one more indirection. This way would further complicate SBCL's TLS access because macros and code generation assume that TLS does not require any indirection. This is clearly the best way to go but it require more changes.

Currently TLS is implemented as option 2. On initialization, we take the slot 63 (or fail if we couldn't - but I can't imagine the situation where this can happen). When windows-threads will be merged to SBCL, we should consider the option 3 because if implemented now, the change would be more than necessary for windows threading support.

TLS notes:

1. This only applies to Win32. Win64 is very different

2. Clozure CL, on the other hand, uses ES segment register and undocument Win32 functions to allocate a segment and store it in a segment register. This is problematic because WOW64 (the Windows subsystem to run Win32 applications in Windows 64) does not preserve the value of ES register during context switches (including thread preemtion). This is the reason why 32-bit version of Clozure CL does not work on Windows 64.

[1]http://en.wikipedia.org/wiki/Win32_Thread_Information_Block

[2]http://www.microsoft.com/msj/archive/s2ce.aspx

[3]http://msdn.microsoft.com/en-us/library/aa232399(VS.60).aspx

[4]http://www.microsoft.com/msj/archive/s2cea.htm

Thread suspension and interruption

Lisp code in SBCL runs in managed environment — SBCL needs to be able to safely suspend threads (because it uses stop-the-world garbage collector) and interrupt them (i.e., call some function in specific thread).

On Unix-like systems, suspending and interrupting threads is simple (but correctly synchronizing threads and writing code that is tolerable to asynchronous interruptions is not simple). This is achieved by using POSIX signals.

Windows API, on the other hand, does not provide equivalent asynchronous interruptions. They have to be emulated. I'll list several ways of emulating them:

1. 'Thread hijacking'. Windows lets stop a thread, examine its context, modify it and restart a thread. This way, another thread may modify the stack and registers in such a way that thread will execute some other function and then return to where it was.

This might seem the way to emulate signals, but it is not. This is racy with Windows internals in several ways[5].

2. QueueUserAPCEx. Windows has support for Asynchronous Procedure Calls (APCs), but only 'kernel APCs' can interrupt thread when it is in user mode. 'kernel APCs' are available from drivers and there is project called QueueUserAPCEx[6] that provides support for them.

This has a very big drawback that it requires a kernel-mode driver to be installed to function correctly. Because of that, I haven't tried it. By the way, pthreads_win32[7] project will use QueueUserAPCEx if it's available.

3. Thread polling. Thread periodically checks if it should suspend or interrupt. This does not require any special support from operating system. But it requires injecting polling into the code and to tolerate potentially infinite delays (they may occur when thread executes a blocking operation).

Among the noted approaches, the only one that really works is the last one. So it's clear that we have no other choice but to implement polling in SBCL threads. Luckily, I didn't even need to do this myself — Paul Khuong implemented 'gc safepoints' for SBCL[8][9]. The safepoints are implement by reading a specific memory location and discarding the result (e.g., with `test %eax, GC_POLL_PAGE_ADDR` instruction). In normal conditions, this instruction will not have effect on the running code. But if the memory page is read-protected or unmapped, this will cause and exception and we will land in exception handler where we can analyze what has happened and what to do next.

In the next post I'll write about how threads are synchronized for timely suspension and interruption.

[5]http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-8&layout=2&eotf=1&sl=ru&tl=en&u=http://blog.not-a-kernel-guy.com/2010/05/04/812

[6]http://www.codeproject.com/KB/threads/QueueUserAPCEx_v2.aspx

[7]http://sourceware.org/pthreads-win32/

[8]http://www.pvk.ca/Blog/LowLevel/VM_tricks_safepoints.html

[9]http://repo.or.cz/w/sbcl/pkhuong.git/shortlog/refs/heads/gc-safe-points

Собрал и выложил текущую версию SBCL'а с поддержкой нитей: https://sites.google.com/site/dmitryvksite/sbcl-distr/sbcl-1.0.43-threads-g002bdc7.msi.

Мне кажется, что из-за плохого обращения с терминологией мы хуже воспринимаем суть вещей, так как наше восприятие оказывается искажено различными ассоциациями.

Вот к примеру, есть такой термин — pattern. Используется во многих контекстах, для лично меня важны два его применения — «design pattern» и pattern как его используют в различных задачах распознавания. По привычке я воспринимал pattern как «шаблон», и это вызывало у меня массу проблем, начиная с того, что я не мог по-нормальному сформулировать предложения с этим словом, заканчивая тем, что я неправильно воспринимал статьи и другие источники информации (что приводило к ошибкам в своих рассуждениях, непониманию результатов).

Недавно я понял, что pattern — это совсем не «шаблон», «образец», а что это «закономерность». Шаблон — это нечто, что определяет свойства других объектов, а закономерность — это то, что отражает свойства других объектов.

Причем словари не всегда помогают в формировании правильного восприятия слова. Например, lingvo в качестве основных значений для pattern дает «образец, модель», «пример, (для подражания), образчик», «модель, шаблон».

Как я вижу, не только я подвержен такому искажению восприятия. Тот же самый перевод «design patterns» как «шаблоны проектирования», а не как «закономерности проектирования», «тенденции проектирования» или «часто используемые приемы проектирования» привел к тому, что многие стали считать design patterns чем-то вроде готовых шаблонов для архитектуры ПО или даже набором правил, которым надо следовать при проектировании.

Надеюсь, что я сказал очередную очевидную вещь.

Собрал виндовый инсталлятор SBCL 1.0.42 (раньше использовал 1.0.40) с поддержкой нитей.

https://sites.google.com/site/dmitryvksite/sbcl-distr/sbcl-1.0.42-threads.msi

Выложил для тестирования бинарную сборку SBCL с нитями в https://sites.google.com/site/dmitryvksite/sbcl-distr/sbcl-1.0.40-threads-2.msi. Если есть возможность прогнать тесты (два основных теста, которые я использовал при отладке я выложил в http://gist.github.com/582848) и отписаться о результатах, было бы здорово.

Продолжаю натыкаться на всякие косяки.

Недавно завершился растянувшийся на несколько недель сеанс отладки — SBCL зависал при загрузке cl-gtk2 из SLIME'а, но ровно до тех пор, пока в буфер *inferior-lisp* не будет введено хоть что-нибудь, после чего загрузка продолжалась успешно; при загрузке cl-gtk2 из консоли не было проблем.

Сперва я грешил на то, что зависание происходит где-то внутри рантайма SBCL из-за дедлока или чего-то подобного. Перепробовал различные варианты отладочного вывода и анализа логов, но это не дало никаких результатов.

Отладка SBCL'а обычным отладчиком невозможна — SBCL использует инструкции «аппаратная точка останова» (int 3) для обработки прерываний, и отладчики постоянно останавливаются (хотя в последних версиях SBCL вместо int 3 можно использовать инструкцию UD2, которая не должна вызывать остановку отладчика). Единственное, что доступно для отладки — стек всех нитей SBCL в момент зависания. Стеки, конечно же, не информативные в плане информации о лисповом коде.

Дихотомией по коду cl-gtk2 удалось найти место зависания — вызов функции gtk-init-check. В момент зависания в стеке был вызов GdiPlus.dll!__DllMainCRTStartup, под которым был вызов kernel32.dll!_LoadLibraryExW, что навеяло определенные соображения о том, что зависает загрузка GdiPlus.dll.

Проверка этой гипотезы показала, что если запустить SBCL из консоли, то вызов (load-shared-object "GdiPlus.dll") завершается без ошибок, а в REPL — зависает.

Непосредственно зависание происходило внутри функции GetFileType, описание которой на MSDN вполне безобидное («Retrieves the file type of the specified file.»). Полезным оказался комментарий в MSDN про то, что GetFileType иногда зависает. Гугление по «GetFileType hangs» выявило следующее.

For instance, GetFileType on a pipe _hangs_ if there is a pending read request, which, BTW, causes the DLL load to hang sometimes, since the C runtime startup in the DLL calls GetFileType on all known handles while setting up the file descriptor table for open/fopen.

Я уже привык к тому, что почти все от microsoft слабо документировано, но к таким неожиданностям заранее невозможно приготовиться. В данной ситуации одновременное наложение нескольких косяков:

  • Отсутствие внятной документации
  • Плохое, неожиданное и рискованное поведение функций работы с вводом-выводом в Win32
  • Тот факт, что базовый элемент win32 — msvcrt использует небезопасную функцию

Главное, что закравшееся сомнение в некорректности поддержки нитей в sbcl развеялось, и я их скоро подготовлю для более широкого тестирования. А с этим багом будет надо придумать, что делать.

Page generated Jan. 20th, 2019 05:45 pm
Powered by Dreamwidth Studios