Category: компьютеры

Category was added automatically. Read all entries about "компьютеры".

wall

Верхний пост

Всем привет.

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

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

scrypt: действительно медленная hash-функция

Есть два способа затруднить атаку перебором:
  • увеличить количество вариантов

  • замедлить вычисление каждого варианта

Первый способ всем хорош (и повсеместен: увеличение битности ключей, хешей и блоков), но не применим в важном частном случае: порождение ключа из пароля. К сожалению, редкий пользователь готов запоминать пароль с энтропией хотя бы в 64 бита :( А ведь для ключей уже давно стандарт не ниже 128.

Специально для этой (и подобных) ситуации предназначен алгоритм scrypt. Помимо очевидной мысли "много-много раз что-нибудь посчитать" в нём задействована ещё одна: "использовать много-много памяти". Идея в том что, если для вычисления функции достаточно нескольких килобайт, очень просто запустить параллельно большое количество экземпляров на GPU или даже на чём-то специальном. А вот если каждому для работы нужно, например, 500 Мб, это уже значительно сложнее.



Сердцем алгоритма является функция ROMix (я точно не уверен, но предполагаю, что RO это от Random Oracle):

# Параметры:
# - hash -- хеш-функция
# - integerify -- функция, некоторым образом преобразующая блок в число. Что-нибудь типа "взять m каких-нибудь бит"
# - B -- исходные данные
# - N -- количество итераций
def ROMix(hash, integerify, B, N):
    X = B
    V = []
    for i in range(N):  # генерируем цепочку из N блоков
        V.append(X)
        X = hash(X)
    for i in range(N);  # случайным образом по ней проходим
        j = integerify(X) % N     # номер следующего блока
        X = hash(X ^ V[j])        # следующий X   
    return X

Очень просто и наглядно. В статье есть доказательство (которое я не смотрел), что функция годная, т.е. что без использования O(N) памяти на её вычисление понадобится O(N2) действий, а значит враг повержен.

Collapse )



У него на сайте есть эталонная реализация, но она очень странная. Странность заключается в том, что параметры N, p, r невозможно задать непосредственно. Можно указать только максимальный размер памяти, максимальную долю от доступной памяти и максимальное время вычисления. А дальше она сама подберёт, оценивая производительность CPU и установленные лимиты. Понятно что при таком подходе получить от одного пароля одинаковые ключи на разных компьютерах -- исключительно редкое везение, так что как это чудо использовать ясно не вполне. Причём это не интеллектуальная обёртка поверх, эта логика встроена в код на самом нижнем уровне, т.е. у него в коде просто не существует функции принимающей N, p, r напрямую. Но, конечно, оттуда можно выбросить всё лишнее и останется только нужное, после чего оно наверное работает (хотя я ещё не проверял).
wall

bitcoin-2


Момент, о котором забыл в прошлый раз. Помните, там были такие транзакции, с входами и выходами, да? И я ещё говорил, что вот, нету денег как таковых, как суммы, которую можно потратить, есть только история транзакций? Вот, всё так и есть, только не сказал, что делать, если нужно перевести кому-то часть суммы. Ну, т.е. собрал блок, заработал 50 коинов, а теперь хочешь перевести кому-то 10 из этих 50-и. Ответ такой: напрямую это сделать невозможно, вход всегда используется полностью, можно перевести только все 50. Другой вопрос, что можно 10 перевести кому-то, а остальные 40 опять себе. На тот же адрес или на другой.

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

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

Как оно работает? [приблизительно]

В качестве хешей используется две функции:

hash256(x) = SHA-256(SHA-256(x)) -- дважды применённое SHA-256. На выходе 32 байта.
hash160(x) = RIPEMD-160(SHA-256(x)) -- сначала SHA-256, а потом RIPEMD-160. На выходе 20 байтов.

Криптография с открытым ключом -- только подпись, применяется ECDSA. Очень мало чего про него знаю, да это и не важно в данном случае. Ну, традиционно: некий открытый ключ, некий закрытый ключ, генерация подписи закрытым, проверка открытым.

Collapse )

Блоки

Я говорил о сложной задаче, которую нужно решить при формировании блока. И, конечно, немножко заработать на этом. Подробности.

Collapse )

Примерно 0.7 * 252 попыток. При реализации "в лоб", мой не очень крутой компьютер считает 10 миллионов хешей за 13 секунд на одном ядре. Пусть будет миллион в секунду, два, если на двух ядрах. Пусть крутой компьютер считает в 50 раз быстрее, итого 100 миллионов в секунду. 0.7 * 252 это примерно 2.8 * 1015, делим на 100 миллионов, получаем 2.8 * 107 секунд. Это 324 дня непрерывной работы. Давайте трезво оценивать наши шансы. Поскольку nonce это последний элемент структуры, кажется, вычисление первого SHA можно сильно ускорить, вычислив его от неполной структуры, и потом завершая с разными nonce-ами. Но даже если мы сведём время его вычисления к 0, это сократит работу всего в два раза, там же ещё второй SHA поверх.

Пусть возможна гораздо более оптимальная реализация. Но и тут предел виден: частоты процессоров выше 4ГГц пока не поднимаются, вычислить хеш меньше чем за 400 ассемблерных инструкций, кажется, слегка оптимистично, SHA не настолько просто устроен, так что не больше 10 миллионов в секунду на ядро. Пусть 10 ядер, вот и есть те же 100 миллионов на компьютер.

Вот табличка со статистикой по разному железу, сравнивающая скорость майнинга. Если коротко, то рулят графические карты, обычные процессоры и близко не валяются. Правда, самое крутое, что там было -- конфигурация с тремя AMD Radeon HD 6990 -- даёт 2094 миллиона хешей в секунду. Всего в 20 раз быстрее, чем рассмотренный выше условный компьютер. Для процессоров лучший результат -- 115 миллионов на 4-процессорной машине с 48-ю ядрами.

В общем, на одном компьютере с теми самыми видеокартами, 16 дней, не меньше. Непрерывной работы. Для вероятности 1/2.

Ещё есть новый и старый калькуляторы, позволяющие оценить ожидаемую прибыльность. Сложность там измеряется в неких условных единицах, стандартных для биткоинов, это производная от описанной выше сложности, текущую можно узнать здесь. Ну и аккуратнее с числами, новый просит количество миллионов хешей в секунду, старый -- тысяч в секунду. Новый оптимистично считает, что каждая попытка приносит 1/вероятность от биткоина и выдаёт "заработанную" сумму в день-неделю-месяц, старый считает, сколько дней нужно работать на 50% и на 95%. Оценки очень похожи на мои.

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

Upd: в комментах объяснили, что теория вероятностей сосёт всё не так грустно и на самом деле есть способы.
wall

PowerPC: user-level программирование

Есть очень интересные моменты (собственно, все что после "Введения" и "Регистров" :)), и вообще очень своеобразное впечатление от архитектуры. Не могу пока сказать про "в целом", но в мелочах -- строга, стройна и логична, как кристаллическая решётка. Она, скажем так, во многом "алгебраически полна". Т.е. реализованы просто все возможные варианты поведения, все возможные комбинации флагов, а не произвольно выбранное подмножество. x86 на этом фоне выглядит, гм, "творческим беспорядком" в лучшем случае :)

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

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )
wall

PowerPC: краткая история

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

До начала

История начинается в 1974-м году. Сотрудник IBM John Cocke разрабатывал машину для обработки телефонных звонков; она должна была работать очень шустро, на сама обработка была не сложной. Его идея была в том, чтобы выкинуть из процессора все сложные команды, тогда простые он сможет обрабатывать за один такт. Эта идея вылилась в архитектуру, которую потом назовут RISC. Проект свернули, но архитектура осталась, и показалась настолько многообещающей, что над ней продолжили работу. Проект назвали 801, в честь номера здания, в котором проходила разработка.

Collapse )

Ссылки

The evolution of RISC technology at IBM John Cocke, V. Markshtein, 1990
Power Architecture: A High-Performance Architecture with a History, примерно 1994-й год, есть описание отличий PowerPC от ранних моделей POWER.
27 years of IBM RISC (заканчивается на 2004-м)
POWER to the people: A history of chipmaking at IBM Хорошая большая статья 2005-го года.
The Rise to POWER три статьи из журнала "Linux User & Developer", 2005-й год.
IBM POWER Systems Overview Про системы, которые из процессоров строятся, с картинками.
Power Architecture Silicon Roadmap примерный список моделей на данный момент (начинается с 2003-го, заканчивается 2008-м).

Upd: Наконец я двинулся дальше: PowerPC: user-level программирование
wall

Виртуальная память - 1 (дополнение)

Предыдущая часть тут.

Intel x86 (32-битные): дополнительные главы


Описанные до сих пор возможности относятся примерно к 486-му. Но прогресс не стоит на месте! Иначе же не впарить лохам новые процессоры. Много нового и интересного было реализовано инженерами Intel в последующих поколениях x86.

Глобальные страницы (начиная с Pentium Pro)

Начнём с простого. На картинках, изображавших PTE и PDE серым цветом был закрашен 8-й бит. Сорвём же покров.

Collapse )

Пробиваем барьер 4 Гб: зачем и как

Сначала рассмотрим постановку задачи. Проблема в том, что линейный адрес у нас по прежнему 32 бита. А, поскольку для нормальной работы приложений преобразование линейного адреса в физический должно быть однозначным, больше чем в 32 бита его преобразовать не получится. И зачем нам тогда 36 разрядов на шине и 64 Гб памяти?

Затем, что преобразование действительно должно быть однозначным, но может быть переключаемым. И есть два основанных на этом юз-кейса:

  • Посредством каких-нибудь ОС-специфик заклинаний пользовательский процесс может попросить ОС отобразить часть его адресного пространства куда-нибудь в другое место в ОЗУ. Поработать там, а потом переключиться обратно. А потом ещё раз обратно. А потом ещё куда-нибудь... Так, манипулируя отображением на разные части ОЗУ, можно делать вид, что много-много памяти доступно почти напрямую. Очень неудобно, но куда деваться на 32-х разрядном процессоре. В Windows есть система соответствующих заклинаний.

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

Перейдём к вопросу "как". В рамках существующей схемы преобразований адресовать 64 Гб нам мешают только слишком короткие адреса в CR3, PDE и PTE. С PDE и PTE всё должно быть понятно, а регистр CR3 я вам раньше не показывал. Вот он какой (до решительных изменений):

4.10 КБ

На адрес отведено 20 бит, именно поэтому каталог страниц должен быть выровнен по границе 4 Кб.

Больше в процессоре физические адреса не употребляются нигде (точнее, я долго вспоминал, но ничего не придумал, если кто знает -- подскажите). Все остальные адреса -- логические, в крайнем случае -- линейные (в инструкциях lgdt, lidt, в отладочных регистрах). А, значит, если разрулим тут -- разрулим везде, остальные даже и не заметят?

.. нет, не значит :) На процессоре жизнь не заканчивается. Проблемы с поддержкой адресов старше 4 Гб могут быть у всякой периферии в режиме DMA. Ну и у драйверов, соответственно. Вот немного на эту тему. Но не будем о грустном.

Пробиваем барьер 4 Гб - I (начиная с Pentium Pro)

Очередной флаг из регистра CR4 называется Physical Address Extension (PAE, бит 5). И он всё меняет.

Collapse )



Всё, вроде про виртуальную память в x86 больше сказать нечего :) Нас ждёт PowerPC.
wall

Виртуальная память - 1

Пора платить долги. Теоретическое введение было тут. Перейдём к реализации.

Вам не повезло. Или наоборот -- повезло. Как посмотреть. В общем, тему защищённого режима x86 я знаю довольно туго. Поэтому получилось длинно, подробно и с кучей ссылок свои на собственные статьи :) Вот только код пока заленился писать. Придётся, конечно, но чуть позже.

Разбил на две части, иначе как-то многовато, слишком высока вероятность, что не прочитает никто :)


Intel x86 (32-битные)


Про устройство памяти в защищённом режиме Intel x86 с отключенной страничной адресацией я подробно писал тут.

Внимательный читатель мог заметить, что я переполз на народ-ру. Это связано с тем, что писем-нет сошёл с ума. Переполз буквально недавно, пока частично и коряво. Когда-нибудь (ха-ха) сделаю это менее коряво. А ещё мне хочется всё нафиг переписать, но тоже, видимо, чуть позже.

Кратко напомню основные тезисы.
  • Адрес, выставляемый процессором на системную шину называется физическим. В рассматриваемой серии Intel x86 максимум -- 36-и разрядов. Для краткости "физическое адресное пространство" я буду по бытовому называть "ОЗУ".

  • Адреса, которые используют прикладные программисты -- логические, имеют форму <сегмент>:<смещение>. Смещение -- 32 разряда.

  • Логические адреса преобразуются в линейные, по формуле <база сегмента> + <смещение>. В типичной современной ОС базы типичных сегментов -- 0 (могут быть специальные сегменты, например сегмент FS в Windows NT). Линейный адрес тоже ограничен 32-я разрядами (да, действительно можно устроить переполнение).

  • Линейные адреса преобразуются в физические. Если страничная адресация отключена, то <физический> = <линейный>. Если включена, то начинается то, ради чего мы тут собрались :)

Итак, табличная адресация включена.

Collapse )



На этом мы завершили основную стройную картину. Дальше -- всякие подробности.
wall

Виртуальная память - 0

Скорее всего, все знают, как устроена виртуальная память в Intel x86 ...

Не. Это вряд ли.

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

Это должен был быть один большой пост. Но он получается слишком большой и я его уже пишу слишком долго. Поэтому пусть будет много маленьких.

[Ликбез] Виртуальная память: что это и зачем

Вдруг кто-то не знал или забыл.

Итак: процессор, память, многозадачная операционная система, много задач (ака процессов). У каждого процесса есть какой-то исполняемый код, какие-то данные, чтобы всё это работало оно должно находиться в памяти. И тут возникает несколько проблем:
  • Процессы не должны мешать друг другу. В частности один процесс не должен иметь возможность случайно поменять данные/код другого процесса, иначе из-за ошибок в одном процессе будут падать все остальные (если такая возможность нужна, пусть попросит явно, это отдельный разговор).

  • Памяти мало. Всем сразу не хватает.

  • Памяти мало. А она ещё и фрагментируется. Допустим, загрузили процесс в память, за ним загрузили следующий, потом первый выгрузили. Осталась дырка. Эту память можно использовать только если будет загружаться процесс, по размеру не превышающий первый.

  • Вообще, "размер процесса" понятие очень условное. Память выделяется из кучи, памяти нужно то мало, то много, дать процессу один кусок навсегда -- очень не гибко

  • Памяти мало. Часто разные процессы используют один и тот же код. Разделяемые библиотеки, или просто одна и та же программа выполняется. Хорошо бы что бы при этом в памяти была только одна копия кода.

Для всего этого придумали сегментную виртуальную память, но она не удобным образом решала не все проблемы. Поэтому ещё немного подумали и придумали страничную виртуальную память. Это было настолько давно, что даже старики уже помнят только последнюю. И когда говорят "виртуальная память" имеется ввиду именно она. Но я начну свой рассказ с начала.

Сегментная виртуальная память

Сегментная виртуальная память требует сегментной адресации.

Простите, но что это такое я описывать не буду. Длинно, нужно рисовать картинки, не очень важно, да и по ходу разберётесь.

Т.е. процесс использует свои сегменты и в чужие не лезет. Это не сложно, это проверяется на уровне сегментных регистров: при попытке использовать сегмент, который нельзя, ОС получает тревожный сигнал (ака исключение), а процесс получает по башке (например, segmentation fault). Этим отличается защищённый режим от реального.

Термины реальный и защищённый режим вообще-то относятся к x86. В данном случае я применяю их нестрого, отношу к "защищённому режиму" те возможности, которые необходимы для реализации многозадачной ОС и которых не было в реальном режиме x86.

Это решение первой проблемы, но это ещё не виртуальная память.

Тут важно отметить, что процесс адресует память относительно начала сегмента, а где это начало он, по хорошему, понятия не имеет. А если имеет, то это ошибка проектирования ОС: не должен. Это ещё одно отличие защищённого режима от реального. А виртуальная память начинается с того, что ОС может временно выгрузить какой-то сегмент процесса из памяти, а когда этот сегмент опять понадобится процессу -- снова загрузить, возможно -- в другое место физической памяти (это термин; да, вот такое странное представление о физике).

Ну, допустим, как-то так:
  • Есть редко работающий процесс. Например, он отзывается на какие-то внешние события, типа прихода данных из сети.

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

  • И вот доходит дело до этого процесса. Он пытается обратиться к своему сегменту данных... Но тот помечен как выгруженный. ОС получает тревожный сигнал, загружает сегмент в память (возможно, выгрузив для этого что-то не нужное), помечает сегмент как нормальный, прописывает ему новый базовый адрес и просит процесс повторить попытку. Как в жизни.

Кто понимает, почему x86 не может так работать -- респект и уважуха :) Ну да, там всё будет немного сложнее, но это уже будет глубокий оффтопик.

Upd: перечитывал пост -- сам еле вспомнил, что имел виду :) Речь о скрытых частях сегментных регистров. Скажем так, недостаточно пометить сегмент как выгруженный в таблице, нужно инвалидировать все кеши. И потом их все обновить, а не просто "повторить заново".


Таким образом, выгружая и загружая, можно выполнять больше процессов, чем у нас памяти. Более того, разные процессы могут ссылаться на один и тот же сегмент кода, значит можно и сэкономить. Сложно с:
  • динамическим выделением памяти (в принципе решаемо, но тяжело)

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

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

Страничная виртуальная память

Несложно заметить, что сегментная виртуальная память работает только за счёт того, что процесс адресует физическую память не напрямую, а немного косвенно. И, влезая в промежуточный уровень, ОС может незаметно для процесса химичить с памятью. Увеличиваем степень косвенности -- увеличиваем химические возможности ОС. По этому пути и пошли.

Итак, процессу предоставляется виртуальное адресное пространство (ВАП), каждому своё. Оно большое. По нонешним прогрессивным временам адресуемая область от 0 до 264-1, недавно стандартом было от 0 до 232-1. Это много, особенно если учесть что процессов не один, а физической памяти, скажем, 256 Мб, т.е. даже на одного не хватает.

Но оно на то и большое, чтобы быть с запасом. Считается, что большая его часть никогда не понадобится большей части процессов. Т.е. в этом огромном ВАП есть небольшие островки используемой памяти. Процесс может запросить себе дополнительный островок, или отпустить какой-то из используемых... Речь не про ограничения, расчёт именно на то, что их на самом деле не нужно слишком много.

Дальше, ВАП разбито на небольшие блоки одинакового размера. К примеру, по 4096 байт. И на такие же блоки разбита физическая память. Блоки называются страницами.

Соответствие между используемыми островками ВАП и физической памятью происходит постранично. Т.е. ОС знает, что такой-то странице из ВАП такого-то процесса соответствует такая-то страница физической памяти. Есть какая-то таблица или что-то в этом роде. Неиспользуемым частям ВАП не соответствует ничего.

Это и есть дополнительный уровень косвенности.

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

  • меньше дискретность

  • В пределах ВАП элементарно регулируется объём используемой памяти, с точностью до страницы можно помечать память как используемую или как неиспользуемую процессом.

Что ещё интересного нужно отметить в этом красивом решении:
  • Адресное пространство других процессов оказывается за пределами языка. Оно просто не адресуемо, нет таких адресов, которые ссылаются на другой процесс. Чтобы как-то читать/писать в память других процессов нужно специально думать.

  • При попытке обратиться к неиспользуемой памяти, процесс тоже получит от ОС по башке.

To be continue... Следующая серия про x86, а дальше начнётся что-нибудь более интересное
wall

Эти забавные жи.. лезяки

Вчера сидел дома, разбирал барахло, оставшееся на компьютере от института, нашёл потрясающую вещь. В папочке labs (лабораторные) лежит папочка с названием Orgazm :) Как вы думаете, что это?

Collapse )

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