18/10/2022

Оптимизация кода (1): О вызовах функций

Недавно я увидел следующую рекомендацию по рефакторингу кода с целью оптимизации:

Изначальный вариантОптимизированный вариант
return pow (base, exp/2) * pow (base, exp/2);let result = pow (base, exp/2); return result * result;

В книге было написано, что результатом такого рефакторинга будет увеличение скорости работы представленного участка кода. Но почему такой рефакторинг должен привести к ускорению работы этого кода? Большинство авторов/советчиков/специалистов не раскрывают суть своих советов и не дают понимания почему что-либо нужно делать так или иначе. Если вам интересно действительно ли здесь произошло ускорение работы и за счёт чего, то читайте — эта заметка для вас. В ней я рассмотрю, что происходит на вычислительной машине в данной ситуации, чем достигается результат, поясню как именно происходит оптимизация и дам информацию для некоторого понимания «масштаба» этой оптимизации. Пояснения в этой заметке раскрывают суть подобной оптимизации не только в данном случае — а в общем. Вы сможете применять это во множестве подобных ситуаций в вашей практике.

По синтаксису можно предположить, что представленный участок кода написан на JavaScript'е. Я же буду работать на общепринятых языках ИТ/ВТ — С, Aseembler x86_64 и стандартном ABI x86_64.

Для начала мы видим, что автор, ценой добавления ещё одной переменной, сократила вызовы функции pow () в два раза. Рассмотрим, что происходит при вызове функции pow (). Её прототип выглядит следующим образом:

double pow (double x, double y);

Из прототипа понятно, что функция работает с параметрами с плавающей точкой и возвращает такой же результат, а это значит, что она будет задействовать сопроцессор (FPU).

Сокращение вызовов функции pow () действительно даёт оптимизацию, и вот почему. Вызов любой функции требует ощутимых накладных расходов. Рассмотрим, что происходит на центральном процессоре при вызове функции в общем, и в частности при вызове функции pow (). В скобках, рядом с командами процессора, стоит приблизительное количество «циклов» (микроопераций) процессора на команду. Рассматриваем на примере x86-ой машины:

1. (При необходимости) вычисление или каким-то иным образом получение всех входных параметров, передаваемых функции (в данном примере это вычисление выражения exp/2). Здесь возможна работа с памятью (а она медленная) и вызовы других, вложенных функций. Если они есть, то стоит пройти все их начиная с этого же пункта.

2. «Раскладывание» параметров, вычисленных или полученных на предыдущем этапе в соответствии с ABI. После вычисления их, они могут оказаться в «местах» (память, регистры), не соответствующих сигнатуре рассматриваемой функции. Это некоторое количество команд mov (~1).

3. Вызов команды call (~10), которая, в свою очередь, сохраняет адрес возврата в стеке, затем осуществляет переход потока выполнения на (указанный адрес) рассматриваемой нами функции.

4. Сама функция pow (), как и любая другая, имеет в себе «преамбулу» (или «пролог»). В этой секции кода происходит сохранение регистров общего назначения путём выполнения нескольких команд семейства push, резервирование пространства в стеке для внутренних нужд функции несколькими манипуляциями с указателем стека. Напомним, что всё это уже происходит один раз в нашей, вызывающей функции.

5. Так как pow () работает с числами с плавающей точкой, она должна сохранить регистры и состояние сопроцессора — так называемую «среду сопроцессора», включающую в себя стек сопроцессора, регистры его состояния, управления, тегов, указатели данных и команд. Так же функция должна сбросить состояние FPU при входе, так как неизвестно в каком состоянии он будет к этому моменту. К счастью у нас есть простые команды для сохранения всей среды сопроцессора — fsave/fnsave (120-150 и более) и finit/fninit (15-20 и более) — для сброса его состояния. Как эти, так и описанные ниже команды восстановления среды FPU, достаточно тяжёлые, так как работают с достаточно большим объёмом информации — всей средой сопроцессора и с памятью (а она, не забываем, у нас — медленная).

6. pow (), вероятно, имеет множество проверок и инициализацию локальных переменных в своей реализации, а они нам здесь не нужны.

7. Реализация самих вычислений функции. При работе с FPU, есть вероятность необходимости вызова команды fwait — дождаться выполнения операции на FPU (на x86 FPU работает параллельно с CPU).

8. После завершения своей работы, функции нужно восстановить регистры FPU и его состояние (что так же уже, возможно, делается в нашей функции). Это команда frstor (~100).

9. В конце функции есть «эпилог», включающий в себя восстановление состояния стека — некоторые манипуляции с указателем стека и регистров общего назначения CPU при выходе — выполнение нескольких команд семейства pop.

10. По завершению вызывается команда ret (15-25), которая извлекает адрес возврата из стека и изменяет указатель текущей инструкции процессора на этот адрес. Таким образом, модуль выборки команд x86, после окончания обработки команды ret, начнёт загружать и выполнять команды с адреса, хранящегося в указателе текущей инструкции.

На ARM'е накладные расходы будут схожими.

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

Но есть и ещё один нюанс. Мы никогда не знаем сколько раз операционная система переключит контекст нашего приложения (в данной ситуации — функции), пока оно работает. А любая, современная операционная система работает по принципу вытесняющей многозадачности. Следовательно, чем меньше список команд, требуемый для получения результата — тем больше вероятность, что наш код будет прерван меньшее количество раз — наша задача будет делиться на меньшее количество квантов выделяемого времени. В критических ко времени вычислениях, когда результат зависит от внешних обстоятельств, например — поток данных, приходящих по сети, такая оптимизация может глобально улучшить результат работы приложения (либо и вовсе спасти код/алгоритм от признания непригодным).

Из этого можно сделать вывод, что такая оптимизация особенно желательна в критичных местах — в «верхних половинах» kernel-space (там лучше вообще не делать никаких вычислений, но мы рассматриваем оптимизацию через сокращение количества вызовов функций в общем), в обработчиках прерываний на Bare-Metal/RTOS.

Теперь опишем, что происходит в оптимизированном варианте. Умножая, в данной ситуации, число само на себя, без вызова функции, мы всего лишь пишем одну команду из семейства fmul, которая в упрощённом варианте (при правильном использовании) умножает два верхних регистра FPU и кладёт результат в самый верхний — ST(0). Который по правилам ABI x86_64, в свою очередь, является возвращаемым значением функции, работающей с числами с плавающей точкой. А если мы пойдём дальше, и сами будем писать код этих операций, то мы сделаем так, чтобы к моменту этого умножения, у нас операнды были уже в двух верхних регистрах FPU, в правильной последовательности. Вот какая оптимизация происходит — практически автоматическая работа процессора на нас.

Кто-то может возразить, что x86-ая машина имеет множество оптимизаций и, что, благодаря им, многие операции из рассмотренного участка кода будут выполнены в параллель, на опережение, или вовсе опущены. Да, это так. Но зачем нам грузить вычислительную машину лишними операциями, когда мы можем избежать их на этапе написания кода? Пусть она использует свои возможности для оптимизации чего-то другого.

P.S.
По описанным выше причинам, предостерегу вас от достаточно очевидного манёвра с этим участком кода. А именно, использовать вместо умножения вызов всё той же функции pow () с result в качестве первого параметра и двойкой — в качестве второго. Умножение числа на само себя — есть возведение его в квадрат. Математически и идеологически, кому-то это может показаться правильнее или «красивее», но технически — правильнее так, как мы рассмотрели. В противном случае это будет «пример плохого кода».

P.P.S.
А вот, например, сократить количество машинных операций, передавая в функцию выражение exp/2 вычисленное заранее извне — хороший вариант. Во-первых, внутри функции не будет заниматься лишнее место на стеке (для проведения этой операции). Во-вторых, при множественном вызове такой функции, с одинаковым значением какого-то из параметров, сократится время на вычисления — он будет вычислен единожды в вызывающей функции и затем повторно использоваться. А если у нас exp/2 будет равно двойке, то и вовсе проще дважды умножить base на себя и выйти, вернув этот результат.

05/01/2022

System concepts (1): BSS — long forgotten but ever-present

In this post we'll take a look at one interesting concept of modern operating systems — BSS. Maybe some of you have not heard of it at all; some of you may think of it as of some sort of ancient thing and suppose it is not used these days. In first part of this post we will examine the purpose it was ever invented for. In second part we'll show how it is used these days ubiquitously even if you don't know about it.

Historically, BSS stands for "Block Started by Symbol" or "Block Starting Symbol". But we will not deepen in history because these days none of that acronym is meaningful.

Technically, BSS is a section of data in (object or executable) file. If it is a section, you may suppose we can declare it in the assembly language with .section directive. Well, that's right. Let's do it.

        .section .bss
	.lcomm var, 1 #1000

	.global main
	.text
    main:
	xorq %rax, %rax
        retq

By the way, modern assembly translators do not require keyword .section, .bss is enough. 

Let's explain what is done here. We declared .bss section with a variable named var in it with a parameter 1 (which may look like a value, but it is not). Compile and look at the resulting a.out, it's size in my case (Linux/GCC) is 16496 bytes. Now we change the parameter 1 to 1000, for example. Compile and look at size of a.out — it remains the same. "What kind of magic is that?!" It's "white" magic and now it's time to explain the whole thing. BSS was invented to save space on disk (or other storage or network bandwidth). And, yes, it's really that "ancient" invention — it originates to the 1950s. You can use it in cases when you don't need to specify values of storage area (variable), for example — to declare buffers which you will write to later, at runtime. You see that variables in .bss are declared in a different manner. It has no .globl directive — it uses .lcomm/.comm instead to specify it's visibility. .lcomm stands for local module visibility, while .comm — for global (some sort of .globl directive). The parameter (1, 1000 in our case or whatever you want) is the size of the buffer. How it works? Linker writes symbol with variable name and address and count of bytes in resulting module. At runtime .bss variables are expanded in memory to specified size and (while it's not standard, usually) initialized with zeroes.

The opposite way to declare zero-filled array is to use .fill directive on regular variable in .data section — in this case all zeroes will be written to resulting module increasing it's size. I'll omit this example here, but you may check it by yourself:

        .data
    big_var:
	.fill 1000000

At this moment you may think — "This is a good idea. But could I use it to optimize my high level language programs with this knowledge?". I've had same thoughts and have checked it. The answer is "yes", moreover — you already often do this. Here starts the second part of our little research.

The short receipt is — just declare your variables as global arrays and initialize them as { 0 }. Let's prove it:

    char lBSSVar[1] = { 0 };
    int main ()
    {
        return 0;
    }

Compile and check the resulting file size. For example, on my machine a.out is 16496 bytes (same size as a.out I've got from assembly language code). Now change the size of lBSSVar to 1000, recompile and see the size of a.out is not changed.

Let's see if it is BSS or something else by examining assembly code we get of our C-code:

	.globl	lBSSVar
	.bss
	.align 32
	.type	lBSSVar, @object
	.size	lBSSVar, 1000
    lBSSVar:
	.zero	1000

We see in this list (I've posted here the part that we are interested in only) that compiler made .bss section from our C-code. Syntax differs from my raw assembly example but technical idea is the same.

P.S.
The idea to save space in object files I've demonstrated in this post is really old. But as we see in last list syntax may differ. For example, clang uses .zerofill directive to describe uninitialized buffers. Thus different compilers may use different syntax. So, in my my opinion, if you code your application in raw assembly language you can use syntax I've shown in first part of this post — it is a short way to use BSS idea. Second part of this post lets you know how to declare buffers you don't need to initialize in high-level languages saving some extra space on storage devices and a little time loading it.

16/09/2021

Маленький взлом системы (2): заставим процессор выполнить переменную

В прошлой статье (Маленький взлом системы (1): наконец-то вы сможете изменять строки типа char* String) мы рассмотрели как можно писать в область памяти, в которую запись запрещена. Сегодня мы разовьём эту тему и попробуем выполнить переменную. Начнём с подготовительных работ. Как и в прошлый раз, нам придётся изменить режим доступа к памяти, так чтобы её можно было исполнять, то есть, чтобы выполнить call или jmp на неё. Для этого объявим переменную следующим образом:

uint8_t lMagicCode [] = { };

Содержание её мы рассмотрим ниже. А сейчас выполним установку необходимых нам режимов доступа к этой переменной. Здесь повторим действия из примера в предыдущей статьи:

void* lPageBoundary = (void*) ((long) lMagicCode & ~(getpagesize () - 1));
mprotect (lPageBoundary, 1, PROT_EXEC | PROT_WRITE);

Мы добавили режим доступа PROT_EXEC, который и позволит нам выполнить переменную. Как вы заметили, я оставил режим PROT_WRITE. Это сделано потому что MMU работает со страницами. На наших машинах её размер, вероятнее всего будет 4kB, что довольно много и помеченная страница скорее всего заденет область, следующую за интересующей нас переменной. А нам нужен режим чтения и записи для обвязки нашего эксперимента. Поэтому чтобы не схватить SIGSEGV после вызова mprotect, мы выставляем совмещённый режим — запись (которая на x86 MMU не бывает без режима чтения) и выполнение.

Далее нам нужно как-то указать машине, как и когда выполнить эту переменную. На всякий случай помечу: эта переменная сама по себе никогда не выполнится, функция mprotect не запустит её, а лишь пометит, как доступную для выполнения. Перейдём к последнему этапу подготовительных работ на высоком уровне (на уровне C), который заключается в том, чтобы объявить функцию, ссылающуюся на адрес этой переменной, что в последствии, позволит нам выполнять эту переменную.

unsigned int (*NewExit)(unsigned long _ExitCode) = (void*)lMagicCode;

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

unsigned int lResult = NewExit (1);

Пока не надо этого делать — пытаясь выполнить пустую переменную, то есть, выполняя call на адрес пустой переменной, вы по сути дела, «провалитесь» дальше (как было в примере предыдущей статьи с выводом строки), а там может быть что угодно и, скорее всего, данные, даже не похожие на последовательность байт, представляющую собой корректную машинную команду с операндами. Что, вероятнее всего, приведёт к ошибке Illegal instruction.

Далее нам нужно заполнить нашу переменную корректным кодом. Начнём, допустим с возврата, то есть исключим «проваливание» потока выполнения при вызове этой функции. По справочникам найдём код операции ret, который очень простой и равен C3h.

uint8_t lMagicCode [] = { 0xC3 };

На самом деле это retn — return near, то есть ближний возврат или внутрисегментный возврат — возврат в пределах одного сегмента кода.

Теперь можно выполнить нашу функцию, не боясь неопределённых последствий, так как теперь произойдёт следующее: команда call сохранит в стэке адрес возврата равный адресу операнда следующему сразу за ним (адрес call + длинна инструкции call и его операнда), затем перейдёт по указанному адресу (адресу нашей переменной), в которой лежит код команды ret, которая, в свою очередь извлечёт адрес возврата из стэка и выполнит переход по нему.

printf ("The result of NewExit is: %d.\n", lResult);

Сейчас мы будем видеть «мусор» на выходе из функции. Для получения какого-то осмысленного результата, вернём значение. Значение из функции по правилам x86_64 ABI возвращается через регистр «семейства» AX. Мы объявили нашу функцию как возвращающую значение unsigned int, то есть 32 бита. Значит нам нужно записать результат в EAX — 32-битный регистр. Найдём код загрузки константы в EAX — это B8h. При заполнении команды нужно учитывать размерность операнда. Здесь мы не можем написать 0xB8, 0x04. Нам нужно указать всё значение полностью.

В языках высокого уровня это за нас делает компилятор. GAS так же подставляет дополненные значения в зависимости от суффикса мнемонического представления команды, например movl $0x04, %eax запишет в реальный код B804000000h, дополнив нашу четвёрку нулями до длинны long. Здесь это не тот long, о котором мы говорили в моделях памяти (LP64), это long с точки зрения x86-ой машины длинной 32 бита. Некоторые трансляторы даже подбирают код конкретной операции из обобщённого мнемонического представления и дополняют размерность операнда в зависимости от указанных размерностей приёмника и источника.

В противном случае, если мы не распишем все байты составляющие 32-битное значение, последующий код, который мы запишем как следующую инструкцию или операнд, в процессе выборки команды процессором будет воспринят как данные для загрузки в EAX. Поэтому соберём код 0xB8, 0x07, 0x00, 0x00, 0x00. И наша переменная приобретёт следующий вид:

uint8_t lMagicCode [] =
{
  0xB8, 0x07, 0x00, 0x00, 0x00, // movl $0x7, %eax
  0xC3,                         // retn
};

Теперь, вызвав эту функцию как

printf ("The result of NewExit is: %d.\n", NewExit (0));

Мы получим:

The result of NewExit is: 7

Функция названа NewExit. Давайте придадим ей этот смысл. Для этого мы воспользуемся системной функцией под номером 60/3Ch и вызовем её при помощи syscall, которая имеет код операции 0F05h. Операционная система, при вызове системных функций от пользовательских процессов, принимает номер функции в регистре EAX. Писать туда мы уже умеем. Наша переменная с машинным кодом приобретёт такой вид (возврат из этой функции нам уже не нужен):

uint8_t lMagicCode [] =
{
   0xB8, 0x3C, 0, 0, 0, // movl $0x3C, %eax, 3Ch/60 - system call exit()
   0x0F, 0x05,          // syscall
};

У нашей функции есть один параметр. Этот параметр попадёт в возвращаемое значение функции main, то есть код нашей переменной аналогичен функции exit. Вы можете это проверить запустив программу на исполнение и проверив код выхода при помощи echo $?. Вы увидите число переданное вами в функцию NewExit.

Хоть мы и передаём int в качестве параметра, возвращаемое из функции main значение всегда снижается системой до одного байта, поэтому не имеет смысла задавать значения более 255.

Здесь может возникнуть вопрос — «А почему так? Мы так много кода писали для простейших действий, а возвращаемое значение попадает в систему без каких либо операций вообще». Дело в том, что по правилам x86_64 ABI первый параметр, указанный в функции, записывается в регистр RDI. А системная функция exit, 60/3Ch возвращает в систему в качестве кода выхода значение RDI. Так совпало — наше значение «провалилось» насквозь и попало в оболочку, в переменную $? и писать нам для этого действительно ничего не пришлось.

P.S.
Интересно отметить тот факт, что отлаживать участки программы, представленные в виде переменных и сформированные в качестве их содержания, будет проблематично. Это связано с тем, что этот код попадает в секцию .data, которая отладчиком не рассматривается как код. Даже если посмотреть ассемблерный вывод после компилятора, то мы увидим просто переменную, в которой будут числовые значения — перечень наших байт в объявленном массиве.

        .size   lMagicCode, 7
lMagicCode:
        .byte   -72
        .byte   60
        .byte   0
        .byte   0
        .byte   0
        .byte   15
        .byte   5

Ниже приведу всю программу:

#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/mman.h>

int main (void)
{
  uint8_t lMagicCode [] =
  {
//     0xB8, 0x3C, 0, 0, 0,          // movl $0x3C, %eax # 3Ch/60 - system call exit()
//     0x0F, 0x05,                   // syscall
    0xB8, 0x07, 0x00, 0x00, 0x00, // movl $0x7, %eax
    0xC3,                         // retn
  };
  
  void* lPageBoundary = (void*) ((long) lMagicCode & ~(getpagesize () - 1));
  
  mprotect (lPageBoundary, 1, PROT_EXEC | PROT_WRITE);
  
  unsigned int (*NewExit)(unsigned long _ExitCode) = (void*)lMagicCode;
  
  unsigned long lResult = NewExit (2);
  
  printf ("The result of NewExit is: %d. Or will never be printed...\n", NewExit (0));
  
  return 0;
}

08/09/2021

Маленький взлом системы (1): наконец-то вы сможете изменять строки типа char* String

Вряд ли найдутся люди, готовые поспорить с тем, что невозможно сосчитать как часто нам хочется изменить содержание строки объявленной как

char* String = "Hello, World!";

Несмотря на то, что эта операция выглядит абсолютно логично и мы ожидаем от неё весьма конкретного и несложного результата, пытаясь сделать что-то вроде

String[1] = 'a';

мы получаем ошибку сегментации (Segmentation fault и сигнал SIGSEGV). И, как правило, на этом вся разработка заканчивается.

Ни в коем случае не пытайтесь это сделать — ваш процессор немедленно сгорит и все несохранённые данные будут потеряны!

Ошибка сегментации возникает в случае, когда процесс «лезет» в недоступную ему область памяти с целью записи (или чтения, см. ниже). А что это за область памяти такая, в которую мы не можем писать? В нашем примере, это область в сегменте данных, помеченная как память только для чтения — RO DATA. Посмотрим что получается в коде программы, в которой объявлена строка char* String. Из программы типа:

int main ()
{
  char* lString = "Hello, World!";
}

мы получим:

    .section   .rodata
.LC0:
    .string "Hello, World!"

Конечно, можно просто заменить .section .rodata на .section .data, но каждый раз вмешиваться в сборку проекта на не самом удобном этапе — трансляции, мы предлагать не будем.

Я решил рассмотреть функцию POSIX — mprotect(). Функция изменяет условия доступа к области памяти.

Но с этой функцией связана одна ошибка. В документации — как в man, так и в интернете, указано, что mprotect() помечает память начиная от адреса страницы до адреса страницы + длинна в байтах за вычетом единицы. В интернете я случайно нашёл упоминание, что длинна здесь указывается в количестве страниц. Что логично, так как MMU работает со страницами, а не с байтами. На нашем примере я подтвердил это — указывая в качестве длинны единицу я пометил достаточное количество памяти для всех наших переменных, то есть, видимо, mprotect() действительно берёт длину в количестве страниц.

Принимает функция на вход адрес, длину и флаг. В нашем примере нас будет интересовать, флаг и, как ни странно, адрес. Флаг нам нужен PROT_WRITE. А с адресом всё чуть более интересно. Так как MMU работает со страницами, начальный адрес, должен быть кратным размеру страницы. С тем, чтобы получить нужный нам адрес, мы вычислим ближайшую (в меньшую сторону) к интересующей нас переменной границу страницы памяти. Сделаем это мы следующим образом. Запросим размер страницы, сбросим у адреса переменной все правые биты, совпадающие с размером страницы. Проще говоря — обнулим адрес переменной справа на величину размера страницы.

Например: адрес lString равен 555555556004h, размер страницы получаем от системы, в моём случае он оказался равен 4096. Из размера страницы уберём единицу, так как фактически она адресуется с 0 по 4095, получим FFFh. Видно, что страницы с таким размером кратны трём полубайтам или полутора байтам. В нашем примере адрес ближайшей к переменной странице равен 555555556000h. Чтобы вычислить этот, адрес нужно сбросить крайние полтора байта адреса переменной. Инвертировав размер страницы получаем маску для логической операции FFFFFFFFFFFFF000h. Приведём это к типу void*, что даст нам полный размер адреса в памяти для любой архитектуры. В результате получим следующие результаты подготовки:

void* lPageBoundary = (void*) ((long) lStr1 & ~(getpagesize () - 1));
Длину, для нашего эксперимента мы поставим равной одной странице. Размер страницы позволит нам поиграть не только с записью в запретные места, но и с границами переменных.
mprotect (lPageBoundary, 1, PROT_WRITE);

Всё. С этого момента начинаются невиданные до сих пор чудеса. Например, следующая программа выводит «World!», а не столь неприятный и уже надоевший «Segmentation fault»:

#include "string.h"
#include "unistd.h"
#include "stdio.h"
#include "sys/mman.h"

int main ()
{
  char *lStr1 = "Hello";
  char *lStr2 = " orld!";
  void* lPageBoundary = (void*) ((long) lStr1 & ~(getpagesize () - 1));

  // Comment next line to turn magic off:
  mprotect (lPageBoundary, 1, PROT_WRITE);
  lStr2[0] = 'W';
  printf ("%s\n", lStr2);
}

Но я предлагаю пройти дальше и ещё чуть-чуть поиграть с адресами. Как вы можете видеть, я объявил две переменные — lStr1 и lStr2. char* — это переменная типа asciz или LPSZ (Long Pointer to Zero Terminated String) или, по-русски — строка оконченная нулём. Как известно, функции, работающие со строками, определяют их длину и окончание по этому самому нулю. Давайте проверим, что будет, если вместо оконечного нуля lStr1 поставить пробел и вывести эту строку при помощи printf(). Здесь же продемонстрируем что мы можем писать (изменять память) в пределах всей памяти модифицированной функцией mprotect(). Эксперимент с удалением последнего нуля из строки lStr1 я предлагаю реализовать путём записи по адресу строки lStr2 - 1:

lStr2[-1] = ' ';
printf ("%s\n", lStr1);

Так как строки расположены в памяти непосредственно одна за второй, получается, что я удалил завершающий нуль lStr1 и поставил не его место пробел. Соответственно, строка lStr1 перестала быть asciz и по логике, printf() должен «провалиться» дальше. Проверим это, получим вывод:

Hello World!

Всё верно, printf() прошёл до первого завершающего нуля, а им оказался завершающий нуль строки lStr2. Мы получили вывод «совмещённой» строки.

На самом деле это выглядит непривычно только на C. На ассемблере подобная работа с данными является повседневной нормой — например длинна строки (string или ascii/asciz) или массива может быть вычислена вычитанием адреса следующей за ней переменной из её собственного адреса.

Но и это ещё не всё. Возможно, к этому моменту, у вас в голове возникла мысль — «Если можно так, то, может, я смогу изменять значения переменных, объявленных как const»? Ответ положителен — эту давнюю мечту можно реализовать. Но с небольшим нюансом. Как мы знаем, компилятор нам не позволит писать в переменные, объявленные с модификатором const. Попытка сделать:

const char* lStr3 = "hello world!";
lStr3[0] = 'H';

приведёт к:

./mprotect.c:18:12: error: assignment of read-only location '*lStr3'
   lStr3[0] = 'H';
            ^

Для разрешения этой ситуации обманем компилятор следующим образом:

*((char*)lStr3 + 0) = 'H';

Мы взяли адрес от переменной, добавили к нему смещение и по нему прописали, что хотели. Теперь всё собирается и работает. За смещение здесь взят нуль, это не имеет технического смысла. Я написал здесь смещение для того чтобы в полной мере раскрыть форму записи доступа к переменным объявленным как const. По этой форме записи вы можете адресоваться на любой символ строки... и не только на него, и не только вперёд, так как мы «взяли» себе целую страницу.

NB
Вроде и очевидно, но считаю что я должен предупредить. Мы сняли запрет записи на область памяти, возможно вы снимете запрет на большую область памяти. Это значит, что вы можете модифицировать память без какого либо вообще контроля со стороны ОС, MMU и компилятора, так как мы полностью исключили этот функционал. Вы можете писать в эти области памяти, но, если вы хотите сохранить адекватную работоспособность своего кода, вам нужно ещё более тщательно следить за границами областей памяти изменяемых вами!

P.S
Возможно вы заметили, что мы использовали флаг доступа PROT_WRITE, без PROT_READ и, при этом мы читали данные из этих областей. Всё это было так потому что у MMU x86 (а я все эксперименты, за исключением особых пометок, провожу на x86-ой машине) нет режима чтения без записи, поэтому можно поставить PROT_WRITE | PROT_READ, но смысла в этом нет. Если вы хотите поиграть с доступом, вы можете попробовать PROT_NONE. В этом случае вы не будете иметь никакого доступа к странице памяти и даже попытка чтения, например через printf(), приведёт к ошибке сегментации. Эту особенность можно было бы использовать каким-то образом на практике, но это затруднено тем, что мы можем помечать только целую страницу, а они бывают только 4Kb/2Mb/4Mb и 4Gb размером, в зависимости от архитектуры и/или режима работы. 4Kb — довольно много для использования механизмов доступа к памяти в качестве какой-нибудь «ловушки». Хотя, если программа достаточно большая, можно группировать флаги, на изменение которых в какие-то моменты мы хотим реагировать, в блоки по 4Kb и в обработчике сигнала реализовать логику реакции на сработавшее исключение защиты.

23/03/2021

Плохой пример (1): «Advanced» for loop в стиле «senior developer»

В этой небольшой заметке я предлагаю рассмотреть два варианта описания несложного алгоритма. Несложного алгоритма поиска некоторого признака по определённым условиям. Здесь я предлагаю оценить качество двух описаний с точки зрения поддержки — понимания человеком, а не с точки зрения эффективности (скорости выполнения, использования ресурсов). Именно поэтому я использую термин «описание» (может даже стоит назвать это «написанием»), так как алгоритм используется один и тот же — взаимный перебор элементов массива со значениями и элементов массива с условиями. Результат заносится в массив Boolean [] Results. Представьте себе, что вы встречаете следующий участок кода:
for (Integer Counter1 = 0, Flag = 1; Counter1 < Total; Results[Counter1] = (Flag != 0), Counter1++, Flag = 1)
  for (Integer Counter2 = 0; Counter2 < Total - 1; Counter2++)
    if (ConditionArray[Counter2] == Counter1)
      Flag = 0;
Сейчас задумайтесь, сколько времени вам понадобилось бы чтобы понять этот участок? Понять в степени достаточной для того, чтобы вы могли внести коррективу — найти и исправить ошибку, изменить условия. А без вводных данных, что я дал в начале статьи? А если бы вы встретили где-то такой фрагмент, как вы могли бы описать его с тем, чтобы облегчить понимание его другими людьми, или вами же в будущем? Здесь оговоримся, что я обезличил названия переменных и названия счётчиков, массивов и прочих сущностей на практике могут быть несколько более осмысленными.
Рассмотрим «нормальное» написание этого алгоритма. Которое я реализовал в первую очередь, так как это написание первым и приходит в голову (может быть не только мне).
// Проходим по всем элементам:
for (Integer Counter1 = 0; Counter1 < Total; Counter1++)
{
  // Ищем совпадение условий:
  for (Integer Counter2 = 0; Counter2 < Total - 1; Counter2++)
  {
    // Сбрасываем флаг в значение по-умолчанию:
    Results[Counter2] = true;
    if (ConditionArray[Counter2] == Counter1)
    {
      // Выставляем флаг и прерываем цикл. В ситуации, которая меня 
      // привела к написанию этой статьи, дальнейший перебор не имел смысла:
      Results[Counter2] = false;
      break;
    }
  }
}
Всё понятно (на сколько вообще код может быть понятен) и комментарии органично влились в код.
Так откуда вообще взялся фрагмент кода, с которого я начал статью? Я сделал его сам. Как я пришёл к этому? Я начал устранять лишние скобки (как я люблю делать после завершения реализации участка кода). Увлёкшись этим процессом, я вспомнил о том, что цикл for состоит из трёх блоков. Таким образом, перенося по частям алгоритм в эти блоки, я и получил «компактное» представление этого цикла.
Теперь поясню, как я адаптировал «нормальное» написание в ненормальное. Ещё раз сокращённый код (чуть понятнее представил блоки цикла):
for
    (
     Integer Counter1 = 0, Flag = 1;
     Counter1 < Total; 
     Results[Counter1] = (Flag != 0), Counter1++, Flag = 1
    )
  for
      (
        Integer Counter2 = 0;
        Counter2 < Total - 1;
        Counter2++
      )
    if (ConditionArray[Counter2] == Counter1)
      Flag = 0;
Здесь запись флага условия в результирующий массив перенесена в третий блок внешнего цикла for. Конструкция «!= 0» используется для приведения Integer к Boolean, точнее для получения Boolean из Integer'а. По правилам большинства популярных языков программирования false — это ноль, всё остальное — true. Соответственно, выражение «!= 0» даёт true. Для адаптации алгоритма к сокращённому написанию, я применил конструкцию, не являющуюся самой понятной для человека. Впрочем, здесь можно было бы использовать любой «маркер» для передачи признака выполнения искомого условия, тем самым ещё больше запутать описание алгоритма. Почему здесь Integer? Потому что в первом блоке цикла for — блоке инициализации, могут использоваться только переменные одного типа, поэтому мне пришлось работать с флагом как с Integer'ом, смешав его с переменной-счётчиком. В противном случае, мне пришлось бы выносить инициализацию флага за пределы верхнего (первого) цикла. Так же в третий блок перенесён сброс значения флага.
Отметим, что комментирование такого написания алгоритма крайне затруднено. Тут скорее нужно не построчные пояснения, а целый документ, описывающий логику реализованного кода.
Для ещё большего снижения читаемости проверку Condition можно было бы заменить на тернарный оператор, но здесь он не подходит, так как он является конструкцией типа if-then-else и выставляет флаг в ненужное положение в блоке else. В ситуации, где он подошёл бы, можно было бы заставить код выглядеть ещё чуть «круче».
Хотя я писал в начале статьи, что мы здесь не будем рассматривать вопросы эффективности, можно добавить, что компактное исполнение будет работать чуть хуже полноценного. Всё потому, что в полноценном варианте перебор заканчивается (break) при нахождении условия, а в компактном цикл проходит до конца — есть избыточные операции. Эта разница специфична для задачи, в ситуации, где придётся проходить весь массив в поисках всех условий (Condition) этой разницы в производительности не будет.
Завернув нормальное исполнение в компактное, я ужаснулся, тому, что получилось, представив себе, что мне когда-то придётся здесь что-то изменить. На получение нормального, понятного написания потребовалось некоторое время. И в итоге, я заново написал «обычное» написание, мне было проще так поступить, чем «разворачивать» компактный вариант обратно.

Выводы
Простой алгоритм настолько естественно выглядящий, с точки зрения языка и компилятора, оказывается в высокой степени трудно поддерживаемым для человека и даже непригодным к описанию (комментированию). Это говорит нам о том, что нужно писать не максимально «крутой» код, а максимально понятный и легко поддерживаемый.

19/03/2021

Размышления (2): о C++, Java и областях применения их

В прошлой статье (Размышления (1): о C, C++, связи между ними, почему ООП переоценен и последствия этого) я рассмотрел историю развития двух основных парадигм программирования, уместность и неуместность применения их в современных условиях. В этой статье я поднимусь чуть выше, и опишу своё видение применения самих языков, основываясь на технических особенностях их реализаций и обоснованности применения их в областях.

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

И всё бы хорошо, потому что в таких областях применяют ООП и это обосновано. Но разберёмся с техническими особенностями реализации двух самых популярных на данный момент ООП-языков — Java и С++. С++ является компилируемым языком, то есть на выходе мы получаем платформенно-зависимый объектный или исполняемый файл. Java — интерпретируемый язык, условно называемая компиляция на Java заключается в получении промежуточного т.н. «байт-кода», который, в последствии, будет выполняться на JVM (Java Virtual Machine — среда времени выполнения Java). JVM обеспечивает кроссплатформенность и сама по себе является платформенно-зависимым приложением.

Из этого вытекают определённые последствия:
C++ хорошо применять для решения двух задач: разработки высоконагруженных приложений и приложений, работающих в условиях ограниченных ресурсов (что, на самом деле есть одно и то же, только с разных сторон). Как правило, оба вида этих приложений пишутся для узкого круга платформ. Высоконагруженные иногда вовсе для одного сервера или супер-компьютера компании. А работающие в ограниченных условиях — для какого нибудь одного процессора/контроллера. То есть кросс-платформенность в таких ситуациях бывает не нужна. Иногда даже возможность переноса на уровне кода (сборка под другие платформы, портирование) бывает не востребована. А возможности оптимизации, как через сам код C++, так и через применение ассемблерных вставок, безграничны. То есть, исходя из особенностей технической реализации языка C++, использовать его целесообразно для разработки высокоточных с точки зрения вычислительных ресурсов приложений (после C и ассемблера, разумеется) и высоконагруженные сервисы. Без сомнения вам было бы приятно, если бы мой блог (как и другие сайты) загрузился бы и работал в несколько раз быстрее.
Java же разрабатывалась для быстрой разработки кросс-платформенных приложений с относительно низкими порогами вхождения в разработку. На этом языке есть очень мало возможностей что-то оптимизировать (всё это делается путём косвенного воздействия на JVM через свой код). Работают приложения на Java относительно небыстро. А если это «относительно» небыстро умножить на тысячу, миллион запросов/операций/вызовов, получится ощутимо медленно. Зато можно быстро и легко разработать пользовательское (end-user) приложение любой сложности и оно будет работать на всех популярных платформах без переноса (пересборки, перекомпиляции и даже без переконфигурации!).

И что мы видим на практике? В подавляющем большинстве Java используется для разработки enterprise-платформ и web-backend, то есть достаточно критических с точки зрения вычислительных ресурсов систем. А для разработки пользовательских приложений используется C++. Ответом на эту потребность стала кросс-платформенная Qt для разработки пользовательских приложений, в том числе и с GUI, на C++. Да, работает быстро, так как это C++, но писать на C++/Qt несколько сложнее — пороги входа значительно выше, чем на Java и переносимость всё равно обеспечивается только через пересборку. А возможность создавать кроссплатформенные приложения, которой обладает Java из коробки остаётся не востребована вовсе — крупные enterprise-приложения, которые разрабатываются на ней, редко куда-то портируются и бывает так что такой продукт всю свою жизнь работает на одном сервере.

Разработку Enterprise и Web на Java можно понять с финансовой точки зрения — воспользоваться Java для ускорения разработки ПО и повышения безопасности (а на Enterprise и Web она очень важна), заплатив больше за серверные мощности, дешевле чем вкладывать в оптимизацию разрабатываемого ПО и, следовательно, тратить больше времени, разрабатывая их на языке более низкого уровня — C++. А вот разработку end-user-приложений на C++ я понять не могу.

Мне кажется, в сложившейся ситуации, логичнее было бы использовать для разработки пользовательских приложений Java, оставить её на Enterprise и Web, а C++ «вытолкнуть» (скорее оставить, ибо она и так там) на встраиваемую технику и на низкий уровень. В «идеальном» варианте лучше C++ использовать и на Enterprise с Web'ом, но это уже наверное маловероятный сценарий.

Но всё есть так как есть — молодые специалисты тяжело работают, решая несложные задачи на C++ (помним о высоких порогах входа), где часто меньше нужна скорость и больше пригодилась бы кроссплатформенность, а имидж Java опошлен, её область применения искусственно заужена, а уровень оплаты труда так же искусственно завышен.

Что это? Сложившиеся традиции? Как и когда они сложились? Когда и почему всё повернуло в эту сторону?

P.S.
Смоделировать ситуацию, в которой разработка высокоответственных продуктов ведётся на C++, а простых — на Java (что так же снижает барьеры использования пользователями разных платформ), я оставляю вам.

P.P.S
Здесь я сравнивал только применение Java и C++ потому что я имею опыт и (конечно личное) видение проблемы некорректного использования только этих языков. Это не означает, что я не понимаю что конфликты PHP vs Python, Python vs Java, Python vs C++ и пр. так же существуют (а, может, какие-то из этих конфликтов и не существуют). Я не писал о них только потому что не имею достаточного опыта участия в таких проектах или хотя бы наблюдения их.

01/06/2020

Маленькая ассемблерная вставка в мой блог (1): оптимизация выставления переменных состояния

Наблюдая за алгоритмами, по которым работают механические устройства, я начал задумываться — а что, если логика программы сама по себе избыточна? Например, принтер всегда делает какие-то движения — ёрзает кареткой туда-сюда, крутит барабан взад-вперёд и, в итоге, приводит себя в положение, необходимое для работы, игнорируя своё изначальное состояние и, что самое главное — не завися от этого состояния. Это конечно заставляет больше ждать пользователя, но удешевляет устройство так как снижает количество элементов, обеспечивающих обратную связь (или вовсе исключает их) — датчики позиций, счётчики оборотов и положений механизмов. А так же, я полагаю, это упрощает алгоритм и повышает его надёжность — в более высокой степени гарантирует приведение системы к требуемому состоянию за счёт исключения сложных логических операций (вычисление состояния/положения каретки, вычисление расстояния, которое, ей надо пройти). Я обратил внимание на то, что можно делать сначала какие-то безусловные действия (настройки) и лишь затем, модифицировать состояние системы, для приведения её в требуемое и отличное от изначального состояние по условиям. То есть можно снизить количество логики, повысив количество безусловных действий. Но кто-то, возможно, скажет что это приведёт к избыточным действиям (тем более, что я только что описал подобные, избыточные действия механической системы). Это нужно проработать и проверить.
Перейдём в плоскость ИТ/ВТ и конкретно разработки ПО. Представим себе пример — нам нужно выставить какой-то флаг в зависимости от условия — флаг наличия или количества байт в буфере I2C, одно из состояний элемента GUI. Часто люди думают (и пишут) конструкции типа:
if (condition) then
    flag = value_1;
else
    flag = value_2;
или даже:
if (condition) then
    flag = value_1;
if (!condition) then
    flag = value_2;
Я всегда хотел проверить, будет ли вариант:
flag = value_2;
if (condition) then
    flag = value_1;
эффективнее для вычислительной машины. Я предполагал, что такая конструкция должна компилироваться в код, где меньше команд JMP (и сходных — JG, JE, JNE). Чтобы проверить это я написал три варианта решения этой задачи и назвал их «if-then-else», «ternary» и «if-then». if-then-else — самый понятный и, как мне кажется, первый приходящий в голову вариант. С ternary всё понятно — это выставка флага по тернарному оператору. if-then — я назвал вариант, придуманный мной (скорее — который я хочу проверить), где сначала выставляется флаг, затем происходит проверка условия, необходимого для изменения состояния флага и изменение флага если условие истинно, соответственно. Вот эти блоки кода (оформлены в отдельные программы):
// if-then-else:
int main ()
{
    int n = 1;
    if (n < 0xC0FFEE)
        n = 2;
    else
        n = 3;
    return 4;
}
// ternary:
int main ()
{
    int n = 1;
    n = (n < 0xC0FFEE) ? 2 : 3;
    return 4;
}
// if-then:
int main ()
{
    int n = 1;
    n = 2;
    if (n < 0xC0FFEE)
        n = 3;
    return 4;
}
В этих программах я использовал числа 1, 2, 3 и возвращаемое значение 4, чтобы по ним, в последствии, ориентироваться в ассемблерном коде.
Теперь посмотрим как выглядит этот код на ассемблере:
1.file "if-then-else.c"
2.text
3.globl main
4.type main, @function
5main:
6.LFB0:
7.cfi_startproc
8movl $1, -4(%rsp)
9cmpl $12648429, -4(%rsp)
10jg .L2
11movl $2, -4(%rsp)
12jmp .L3
13.L2:
14movl $3, -4(%rsp)
15.L3:
16movl $4, %eax
17ret
18.cfi_endproc
19.LFE0:
20.size main, .-main
21.ident "GCC: (GNU) 9.3.0"
22.section .note.GNU-stack,"",@progbits
1.file "ternary.c"
2.text
3.globl main
4.type main, @function
5main:
6.LFB0:
7.cfi_startproc
8movl $1, -4(%rsp)
9cmpl $12648429, -4(%rsp)
10jg .L2
11movl $2, %eax
12jmp .L3
13.L2:
14movl $3, %eax
15.L3:
16movl %eax, -4(%rsp)
17movl $4, %eax
18ret
19.cfi_endproc
20.LFE0:
21.size main, .-main
22.ident "GCC: (GNU) 9.3.0"
23.section .note.GNU-stack,"",@progbits
1.file "if-then.c"
2.text
3.globl main
4.type main, @function
5main:
6.LFB0:
7.cfi_startproc
8movl $1, -4(%rsp)
9movl $2, -4(%rsp)
10cmpl $12648429, -4(%rsp)
11jg .L2
12movl $3, -4(%rsp)
13.L2:
14movl $4, %eax
15ret
16.cfi_endproc
17.LFE0:
18.size main, .-main
19.ident "GCC: (GNU) 9.3.0"
20.section .note.GNU-stack,"",@progbits
Части кода, что одинаковы, затенены серым цветом, а те, что нас нтересуют — выделены в центре. Таким образом мы фокусируемся только на том, что нас интересует, отсекая общие для всех программ участки кода.
Что мы видим:
        movl $1, -4(%rsp)
Здесь мы иницилизируем переменную единицей (именно для того чтобы понять, где начинается интересующий нас код, я это и делаю).
        movl $4, %eax
        ret
Это наш return 4; (именно для того чтобы понять, где заканчивается интересующий нас код, я и возвращаю четвёрку).
Можно видеть, что всё происходящее вполне прозрачно и подтверждает теорию, выдвинутую мною. Теперь мы можем отранжировать методы.
if-then показал себя самым компактным, не только с точки зрения операций, но ещё и тем, что содержит на одну метку меньше, а метки так же хранятся в ELF-файле, что, в нашем случае говорит об экономии места. Стоит отметить, что место экономится гораздо меньше, чем скорость — метка в файл записывается один раз, грузится тоже один раз, а вот исполняться каждый такой участок кода в программе может неисчислимое количество раз.
На втором месте if-then-else. Вполне логично больше на одну метку и на одну операцию перехода.
А вот ternary лично меня удивил. Это самый худший вариант, как с точки зрения размера, так и с точки зрения скорости (количества операций). В этой ситуации GCC сгенерировал код, который, кроме всех операций, что выполняет в варианте if-then-else, зачем-то работает сначала через регистр EAX, а затем перекладывает значение в переменную.
Вывод: да, вариант if-then эффективнее с точки зрения выполнения на машине. Хотя такая конструкция может несколько хуже восприниматься человеком — «Как это, сначала что-то приравнивается, а потом проверяется условие, и если оно не выполняется, то флаг вообще остаётся без внимания» — как будто кто-то забыл дописать строчку. Но если люди часто используют тернарную форму записи, которая вообще «не для людей» и считают себя «сеньорами», то я думаю мы можем писать в стиле if-then и тоже вполне обосновано считать себя сеньорами.
Здесь добавлю, что мы можем пользоваться этим методом не только для выставления флагов типа 1/0 или типа Boolean — метод if-then можно использовать и для выставления иных изначальных значений — цвет кнопки зелёный, а если имеется состояние ошибки, то выставлять его в красный; количество байт в буфере — ноль, а если есть что-то на входе, то выставляем этот счётчик в нужное количество и т.д..
Так же методом if-then можно экономить (хоть и не так много в процентном соотношении) и на более сложных конструкциях ветвления: цвет кнопки зелёный, если состояние ошибки — выставить в красный, если состояние промежуточное — выставить в оранжевый. Это сэкономит не 50%, как в вышеописанных ситуациях, а количество состояний за вычетом одного перехода и одной метки. Используя метод if-then, стоит вначале выставлять переменную в максимально часто возникающее состояние (если это можно продумать) — в таком случае часто будет происходить одна операция типа MOV, за ней одна или более операций типа JMP и минимальное количество случаев с повторным MOV, так как вы уже выставили флаг в максимально часто возникающее состояние.
В следующих статьях можно будет рассмотреть что получается из иных стандартных языковых конструкциях и как можно на них срезать углы.