Easyelectronics.ru

Электроника для всех
Текущее время: 01 окт 2020, 18:23

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/5шт. два слоя. $5/5шт. четыре слоя
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 98 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:42 
Старожил

Зарегистрирован: 05 дек 2015, 16:56
Сообщения: 315
MasterAlexei писал(а):
Gipsy писал(а):
А почему вы этот буфер назвали циклическим(кольцевым)? Ведь он не работает как кольцо.
Допустим в процессе приёма RW перепрыгнет границу и начнёт указывать на 0-й элемент. RD ещё не успел дочитать данные и указывает к примеру на 10-й элемент. Ничто не мешает ни RD дочитать ранее принятые данные, ни RW продолжать приём и писать в элементы 0..9. Как собственно и должен был бы работать кольцевой буфер.
Но не в вашем случае. Ваш буфер заклинит как только будет пересечена граница массива.

Тут RBUF_MASK(RBUF) & (RBUF).wr обеспечивает цикличность.
Единственно - размер буфера должен быть кратным степени двойки. Иначе да - заклинит.

Должен был обеспечивать.
А на самом деле RBUF_NOTEMPTY (RBUF) ((RBUF).rd < (RBUF).wr) не даст больше ничего прочитать, потому что решит что буфер пуст как только (RBUF).wr станет равным 0.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:42 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 3571
Откуда: Китай, Пекин
Цитата:
Что-то как-то идею не уловил. Как оно сделает запись в буффер атомарной операцией?


смотри чуть выше, обсуждались варианты краха

Цитата:
Значит, загрузил он одну переменную (кстати, хрен его знает какую именно, это дано на откуп оптимизатора, насколько я знаю), и тут пришло прерывание, и обнулило их обе :), и одну даже увеличило на 1. Вышли из прерывания, загрузили другую переменную в регистр. Сравниваем.... старое значение одной с новым значением другой. Ну вот и приехали, собсно.
Или я опять что то упустил?


volatile - гарантированность последовательности опреаций. как написано таки и работает! никаких оптимизаций! никакого кэширования в стеке.

я и сам не знал, а оно вона чё как вышло! случайно написал правильно. да и практика - критерий истины подтвердила.

короче, код на удивление хорошъ.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:43 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
Gipsy писал(а):
MasterAlexei писал(а):
Gipsy писал(а):
А почему вы этот буфер назвали циклическим(кольцевым)? Ведь он не работает как кольцо.
Допустим в процессе приёма RW перепрыгнет границу и начнёт указывать на 0-й элемент. RD ещё не успел дочитать данные и указывает к примеру на 10-й элемент. Ничто не мешает ни RD дочитать ранее принятые данные, ни RW продолжать приём и писать в элементы 0..9. Как собственно и должен был бы работать кольцевой буфер.
Но не в вашем случае. Ваш буфер заклинит как только будет пересечена граница массива.

Тут RBUF_MASK(RBUF) & (RBUF).wr обеспечивает цикличность.
Единственно - размер буфера должен быть кратным степени двойки. Иначе да - заклинит.

Должен был обеспечивать.
А на самом деле RBUF_NOTEMPTY (RBUF) ((RBUF).rd < (RBUF).wr) не даст больше ничего прочитать, потому что решит что буфер пуст как только (RBUF).wr станет равным 0.



Вы невнимательны. ТС не обнуляет wr при переходе за границу буфера. Интересное, хотя и сомнительное решение...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:44 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 3571
Откуда: Китай, Пекин
Цитата:
Оно будет работать.

???
я ж говорю. работает.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:47 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 3571
Откуда: Китай, Пекин
Цитата:
сомнительное решение...


так в ЭТОМ-то как раз и ВЕСЬ смысл никто чужие индексы не трогает, только каждая сторона свои никаких сравнений выхода за границы, красота!

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:51 
Старожил

Зарегистрирован: 05 дек 2015, 16:56
Сообщения: 315
Mirmik писал(а):
Gipsy писал(а):
MasterAlexei писал(а):
Тут RBUF_MASK(RBUF) & (RBUF).wr обеспечивает цикличность.
Единственно - размер буфера должен быть кратным степени двойки. Иначе да - заклинит.

Должен был обеспечивать.
А на самом деле RBUF_NOTEMPTY (RBUF) ((RBUF).rd < (RBUF).wr) не даст больше ничего прочитать, потому что решит что буфер пуст как только (RBUF).wr станет равным 0.



Вы невнимательны. ТС не обнуляет wr при переходе за границу буфера. Интересное, хотя и сомнительное решение...

Да, действительно интересное решение, не обратил внимания.
Но таки сомнительное... надо делать указатели RW RD 64-битными :)
А давайте все писать большими шрифтами :)


Последний раз редактировалось Gipsy 03 май 2016, 18:56, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:54 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
cheblin

Если операции с wr не атомарны, то прерывание может модифицировать wr, в момент работы с ним основного цикла.
Это может привести к последствиям, а может не привести.

У меня, например, не хватает фантазии, чтобы расчитать все возможные варианты.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:55 
Старожил

Зарегистрирован: 20 мар 2013, 11:27
Сообщения: 5358
cheblin писал(а):

так в ЭТОМ-то как раз и ВЕСЬ смысл никто чужие индексы не трогает, только каждая сторона свои

Тоже анализировал свой код и понял, что проблем быть не должно потому, что указатель на последний элемент меняется только внутри прерывания для rx буфера и только в программе для tx буфера. Указатель на первый элемент наоборот меняется только в программе для rx и только в прерывании для tx
Все это специфика работы uart
Тонкий момент только в определении границы
Например в момент чтения программы из rx буфера данные могут быть уже прочитаны, а указатель еще не передвинут. Ничего критичного нет если в этот момент сработает прерывание по rx
Тоже с tx
Достаточно volatile для переменных с указателями


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 18:59 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
axill
Проблема может наступить при неатомарной записи головы...

Может возникнуть ситуация, что после 0xFF последует не 0x100, а 0x1FF... Ну и всякая подобная хрень... Крайне маловероятно, но возможно...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 19:02 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 3571
Откуда: Китай, Пекин
Цитата:
Это может привести к последствиям, а может не привести.

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

всё это время перелапатил интернет в поисках ответа на этот вопрос.
результат этих трудов собственно тут и выложил. volatile -это гарантия.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 19:10 
Старожил

Зарегистрирован: 20 мар 2013, 11:27
Сообщения: 5358
Mirmik писал(а):
axill
Проблема может наступить при неатомарной записи головы...

Может возникнуть ситуация, что после 0xFF последует не 0x100, а 0x1FF... Ну и всякая подобная хрень... Крайне маловероятно, но возможно...


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 19:12 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
axill
...До тех пор, пока вы не станете запрашивать количество накопленных данных. Тут уже может быть критичная ошибка.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 19:16 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
Но, возможно, действительно надо защищать операцию available, а не чтение - запись...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 19:27 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
Любопытно, что в коде библиотеки Ардуино у класса Serial...

availableForWrite защищен от неатомарного доступа, а
available - нет...

Интересно, чем они руководствовались?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 03 май 2016, 21:13 
Старожил

Зарегистрирован: 20 мар 2013, 11:27
Сообщения: 5358
А что критичного в available?
Он может вернуть "нет места", когда место уже освобождается или "пусто", когда данные уже помещены
Ни то ни то не критическая ошибка


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 00:22 
Заглядывает иногда

Зарегистрирован: 18 окт 2014, 00:39
Сообщения: 145
Вот простая, красивая, портабельная реализация кольцевого буфера - http://kargs.net/code/fifo.c


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 00:49 
Старожил

Зарегистрирован: 20 мар 2013, 11:27
Сообщения: 5358
turnon писал(а):
Вот простая, красивая, портабельная реализация кольцевого буфера - http://kargs.net/code/fifo.c


каким образом ограничен выход хвоста за пределы буфера?
Код:
uint8_t FIFO_Get(
        FIFO_BUFFER * b)
{
    uint8_t data_byte = 0;

    if (!FIFO_Empty(b)) {
        data_byte = b->buffer[b->tail % b->buffer_len];
        b->tail++;
    }
    return data_byte;
}


в порядке обмена опытом моя реализация
Show хидер

Show либа


Show пример с uart


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:02 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
axill
Например, он может вернуть наличие 231 байта, когда вы ждете наличие 16-ти при реальном наличии 5-ти, тем самым побуждая вас начать некоректное чтение...

Это, конечно, высосано из пальца, но я все-таки предпочитаю тут перестраховаться.
Таки надежность превыше скорости.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:15 
Старожил

Зарегистрирован: 17 дек 2014, 04:38
Сообщения: 705
2Axill Очень просто - буфер b->buffer[] индексируется остатком от целочисленного деления b->tail на b->buffer_len (то есть размер буфера). Таким образом чему бы не был равен tail остаток от деления всегда будет меньше buffer_len. Таким образом вы будете ходить по кольцу никогда не превышая buffer_len.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:16 
Старожил

Зарегистрирован: 20 мар 2013, 11:27
Сообщения: 5358
void1509 писал(а):
2Axill Очень просто - буфер b->buffer[] индексируется остатком от целочисленного деления b->tail на b->buffer_len (то есть размер буфера). Таким образом чему бы не был равен tail остаток от деления всегда будет меньше buffer_len. Таким образом вы будете ходить по кольцу никогда не превышая buffer_len.

а как с этим быть?
Код:
static volatile unsigned FIFO_Count (
    FIFO_BUFFER const *b)
{
    return (b ? (b->head - b->tail) : 0);
}


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:22 
Старожил

Зарегистрирован: 17 дек 2014, 04:38
Сообщения: 705
если b != null возвращает b->head - b->tail, в противном случае возвращает 0. Короче проверяет существует ли указатель на структуру b, если существует - выполняется вычитание иначе 0.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:31 
Старожил
Аватара пользователя

Зарегистрирован: 06 ноя 2013, 16:07
Сообщения: 711
Откуда: Германия
turnon писал(а):
Вот простая, красивая, портабельная реализация кольцевого буфера - http://kargs.net/code/fifo.c


Та же проблема, что и в обсуждаемой реализации - неатомарность unsigned на восьми-битниках.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:32 
Старожил

Зарегистрирован: 20 мар 2013, 11:27
Сообщения: 5358
void1509 писал(а):
если b != null возвращает b->head - b->tail, в противном случае возвращает 0. Короче проверяет существует ли указатель на структуру b, если существует - выполняется вычитание иначе 0.

переводить язык Си не нужно)
дело в том, что в коде GET выше tail инкрементируется без ограничений
так что результат вычитания может быть очень странный
да и кстати аргумент, что за границы массива мы не выйдет благодаря использованию оператора % состоятелен
но он не объясняет как мы избежим ошибки когда переменная taill при инкрементировании получит переполнение с обрезанием


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:33 
Старожил

Зарегистрирован: 17 дек 2014, 04:38
Сообщения: 705
что значит "неатомарность" на восьмибитниках ? восьмибитники разве многопроцессорные ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Циклический(кольцевой) буфер.
СообщениеДобавлено: 04 май 2016, 01:38 
Старожил
Аватара пользователя

Зарегистрирован: 06 ноя 2013, 16:07
Сообщения: 711
Откуда: Германия
axill писал(а):
а как с этим быть?
Код:
static volatile unsigned FIFO_Count (
    FIFO_BUFFER const *b)
{
    return (b ? (b->head - b->tail) : 0);
}


Переполнение для без знаковых типов - определено, отработает как надо. Т.е. (10 - 250) == 16


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 98 ]  На страницу Пред.  1, 2, 3, 4  След.


Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB