Отговори на тема  [ 37 мнения ]  Отиди на страница Предишна  1, 2, 3  Следваща
JSON Parser 
Автор Съобщение
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Фев 26, 2006 5:52 pm
Мнения: 10356
Местоположение: Добрич
Мнение Re: JSON Parser
Чак да не можеш... хората ракети правят и пак им забива софтуера. Няма невъзможни неща ;-)
Истината е, че обработката на динамични данни в статична памет не е особено добра идея. В случая - да, виждам че има параметър за броя на токъните, което вероятно ограничава рекурсията. Ако всичко останало е ОК, това те защитава от външни атаки. Но на практика по-опасни са собствените проблеми. Примерно ти си сметнал, че за тоя продукт 10 токъна са достатъчни, проверил си колко памет им трябва, настроил си си нишката и всичко е 6. Да, ама след време ти искат да вкараш още малко обработки, примерно да пратиш или получиш данните по SSL. И там малко е мъгла колко памет ти трябва. Като навържеш няколко такива обработки в една нишка или още по-зле като част от обработките се разпръснат в различни нишки и си готов за бедствие. Идва клиента и ти казва ама 10 токъна не са достатъчни, направи ги 20. Естествено параметърчето лесно ще го вдигнеш, но да предвидиш как ще се отрази това, особено на нишки, които не си писал лично... А може би най-коварното е, че подобен проблем не избива веднага, щото ти вдигаш на 20 виждаш че работи и си казваш - стана, няма БУМ. Да ама забравяш за SSL-а или другите обработки и по закона на Мърфи устройство отива на полето и там се случва някой да е накачулил големи сертификати, json-че с много токъни и изобщо всичко е отишло на макс и се получава БУМ, а ти нямаш идея защо.
Затова мразим рекурсии. Много по-добре е когато обработките работят с фиксиран стек. То не винаги е възможно, но поне като порядък да имаш представа и тоя порядък да не зависи от броя на токъни или други параметри. Спестява доста нерви повярвай ми ;-)


Пон Юни 24, 2019 8:46 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 3855
Местоположение: Габрово
Мнение Re: JSON Parser
speedblue написа:
а външни клиенти докато се научат да подават правилни JSON-и бая са се чесали защо им връща грешка

По тази линия защо не им валидирате json-а? Имам предвид на пц преди да го стрелят (или като web услуга, или както искате). Има стандарт за json схеми и чрез него става лесно - много редактори позволяват валидиране в реално време. Така ще спестите мъките да пращат файла и да се чудят какво е станало.
Друга опция е да пуснете същия парсер за пц (инструментче) и клиентите ще могат да прекарват през него своите файлове - така ще знаете дали не удрят на някое ограничение на парсера.

А всички проблеми на рекурсията, дето е описал Миро, са изцяло приложими към динамична памет и нейното изчерпване и/или фрагментиране. Имам предвид че неконтролираното ползване на памет (или какъвто и да е ресурс) води до състезания и борби. Стекът е по същия начин и затова може да доведе до същите проблеми - рекурсията може да изяде неизвестно количество стек, така че пак отиваме на същия подход към проблем както при heap-а - очаква да гръмне на всяко ново "заделяне"(викане) и сме готови да реагираме на грешката без да умрем. Дали е по-лесно или трудно да се направи едното или другото е въпрос на имплементация. Кофтито и в двете е че ще реагират runtime. За стека има инструменти които биха могли да планират използването му още compile time, но рекурсията сигурно няма да хванат. За динамичната също може да се предвиди донякъде, но едва ли със static code checker?
Особено при "свободен трединг" модел, където всеки писач има правото да прецени че му трябва нов тред-два-три. Размива се логиката на работа. Компилаторът би се справил ако нямаше тредове и имаше само статични данни - би хванал почти всички проблеми. Като се появи динамична памет трябват подходящи инструменти за анализ - valgrind, гугълския AddressSanitizer и всякакви безбожно скъпи по-нагоре. Като се появи трединг трябва следващия тул. А той иска да разбира какво и кога се случва - кое е отделен тред, къде се създава, спира, форк-ва и т.н. Ако има стандарт (posix, osek) е лесно, ако е популярна OS (видноус) също ще има достатъчно интерес да има такъв тул.
Според трети важното е да има четливо (т.е. на ниво език) описание на тия неща за да могат да се заложат в компилатора.
Според някои е по-лесно да следиш заделянето и освобождаването, според други не си заслужава труда и има garbace collector-и. Т.е. "ръчно" vs "автоматично" менажиране на паметта.
Номерът е да има достатъчно ясно представяне/описание на какво се случва в програмата, за да могат максимално количество проблеми да се хванат още при компилиране (в един по-добър свят - всички такива). Дали е възможно? Rust имат интересен подход за това - "borrow" - в езика има средства с които да кажеш че дадена променлива е "даваш на заем" на друга функция - т.е. ти вече нямаш право да я ползваш докато не ти я "върнат", а други функции не могат да ползват променливи докато не им бъдат "дадени на заем".
В тая посока съм привърженик на "immutable data" подхода, или както сме го срещали в някой ембедед C продукти - "zero copy". Подходът е че дадена "променлива" след създаването си (инциализирането си) не може повече да бъде променяна 8O Пълен шит е като идея на пръв поглед, нали? Само че не е - да кажем оня json си стои непроменен - каквото е дошло си остава така (immutable) и парсера създава нови "променливи" които са токени или нещо подобно. Тия токени веднъж създадени не се редактират. Т.е. те са поинтъри към характерните точки в оригиналния json (който даже може да е във флаш/ROM).

Тъй де, тезата ми беше че всяко използване на ресурс трябва да бъде контролирано - за статичните такива вече имаме достатъчно ефективен инструмент - компилаторът. За динамичните трябва да се полагат грижи - било то рекурсия която може да изяде стека, било заделяне което може да гръмне или да забрави памет да изтече. На практика е до стил и предпочитания на писача кое ще избере - както и дали ще направи контрол или използва наличния такъв (грешка от малок например).
С трединг модела е подобно, но проблемите са още повече и дисциплината е още по-важна. А по-доброто от дисциплината е проверката на максимално ранен етап - за да се избегне онова че с 20 токена работело някъде, но не и ако в момента ссл-а е в един какъв си стейт. Ако компилаторът каже "нямаш място за 20 токена и 128К за ссл" е най-добре. Ако твърдя че знам как ссл и токените няма да работят в един и същи момент трябва да мога да го опиша на компилатора за да го накарам да се съгласи че няма конфликт.


Пон Юни 24, 2019 9:52 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: JSON Parser
Не е проблем да се парсва json и без рекурсия или динамично алокиране - просто е неудобно и неефективно но определено не е невъзможно т.е. според изискванията се избира един или друг подход.

_________________
Мразя да мразя ...


Пон Юни 24, 2019 11:28 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Фев 26, 2006 5:52 pm
Мнения: 10356
Местоположение: Добрич
Мнение Re: JSON Parser
gicho написа:
А всички проблеми на рекурсията, дето е описал Миро, са изцяло приложими към динамична памет и нейното изчерпване и/или фрагментиране.


Динамичната памет си има своя специфика, но по дефиниция си е ресурс. И като такъв имаш контрол, можеш да си дефинираш функциите за malloc и free и ++оператора new. На по-маловажните може да връщаш грешка, по-важните да им заделиш отделно памет или да изчакват. Изобщо има си чалъми.
За stack usage обаче няма стандартно решение. Трябва да разчиташ на хардуерна защита, но при АРМ забрави за такава. Анализаторите са мижи да те лажим, само в някой тузарски инструменти казват че работят. Ама аз такива не съм виждал на живо ;-) Така че това дето си го мислиш как още на compile time ще хващаш грешки, хвани ми ги и бирата е от мен ;-)

Като цяло с GCC и ARM проблемът със стек юсиджа е много голям. Не е като да не съм търсил решения. Единственото ни спасение е, че избягваме всякакви алгоритми дето имат "скрити" заложби да ядат стек. Така с малко запаси в нишките удържаме пораженията на разумно ниво. А когато все пак се стигне до поражение с малко трикове го хващаме сравнително бързо.


Пон Юни 24, 2019 6:39 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Нед Окт 31, 2004 8:19 pm
Мнения: 4410
Местоположение: Stara Zagora
Мнение Re: JSON Parser
Погледнете библиотеката която съм дал в началото. Идеята е много добра.


Пон Юни 24, 2019 6:54 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: JSON Parser
miro_atc написа:
...
Като цяло с GCC и ARM проблемът със стек юсиджа е много голям. Не е като да не съм търсил решения. Единственото ни спасение е, че избягваме всякакви алгоритми дето имат "скрити" заложби да ядат стек. Така с малко запаси в нишките удържаме пораженията на разумно ниво. А когато все пак се стигне до поражение с малко трикове го хващаме сравнително бързо.

Маркер на дъното на стека и в прекъсване на таймера следиш всички нишки дали не са си омазали стековете - ако са омазали, пишеш в лога каквато диагностична информация можеш да изкараш и ребуутваш - така и така омазването е невъзстановимо. Пак да кажа - няма проблем да се направи парсване на json с има няма 20-30 байта променливи + безброй цикли ... просто е тъпо да се решава проблема по този начин.

_________________
Мразя да мразя ...


Пон Юни 24, 2019 8:36 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Фев 26, 2006 5:52 pm
Мнения: 10356
Местоположение: Добрич
Мнение Re: JSON Parser
palavrov написа:
Маркер на дъното на стека и в прекъсване на таймера следиш всички нишки дали не са си омазали стековете


Малко грубичко всяка милисекунда да чеквам всички нишки ;-)
Ползвам много по-елементарен похват, просто разполагам TCB-то на нишката непосредствено преди стека. Така с 99% вероятност при първия опит за смяна на контекста стига да ексепшън в който си запомням текущата нишка, рестатирам и след рестарта виждам че е софтуерен и си логвам спокойно подробностите.
Проблемът не е в това, проблемът ми е че няма читав статичен анализ. Съответно повечето нишки се оразмеряват на око. И тъй като страх лозе пази повечето са прилично преоразмерени, но никой не смее да ги барне.


Пон Юни 24, 2019 9:26 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: JSON Parser
Абе прав си ... пиша ги и аз малко наизуст - достатъчно е да проверяваш текущата нишка когато я сменяш с друга :)

То и с маркер също не е 100% гаранция, че стека е омазан - може да е омазан и без да се повреди маркера. Но все пак помага де и е сравнително лесно за изпълнение.
Аз не бих сложил TCB-то в стека - ако се омаже как ще знам коя всъщност е тази нишка :)

_________________
Мразя да мразя ...


Пон Юни 24, 2019 9:37 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Фев 26, 2006 5:52 pm
Мнения: 10356
Местоположение: Добрич
Мнение Re: JSON Parser
palavrov написа:
Аз не бих сложил TCB-то в стека - ако се омаже как ще знам коя всъщност е тази нишка :)


ТСВ-то след 4-та архитектура (т.е. от куртекс) е от две части - регистри и указатели. Една част от регистрите се спасяват хардуерно и автоматично, още преди да стигне до смяна на контекста. Тая част си е в стека, щото няма избор. Другата част от ТСВ-то на нишката не е в стека, а точно под стека, така че ако стека прелее първото нещо за омазване е собственото си ТСВ. А в ТСВ-то имаш поне два указателя, които се ползват при смяна на контекста и вероятността да гръмне преди да е приключило със смяната е достатъчно голяма. Указателят към текущата нишка не е нито в стека нито в ТСВ, той е другаде и се променя след смяната на всичко останало. Така че няма проблем.
Разбира се има случаи в които не гърми веднага. Примерно ако имаш функция с много голям стек юсидж, тя обикновено първо си го заделя, т.е. мести стек поинтера. И после маже в произволен порядък, т.е. може да омаже нещо из паметта преди ТСВ-то, може даже да направи няколко свитча, но обикновено накрая си омазва и ТСВ-то и тогава гръмва. Наистина в много редки случаи съм виждал така да прескочи важните указатели или пък да ги омаже с правдоподобни стойности, т.е. да успее да приключи с контекста и да изгубя коя нишка е истинския виновник.


Пон Юни 24, 2019 10:31 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: JSON Parser
А ползвал ли си компилатора да си прави проверка за препълване на стека в пролога на всяка функция?

_________________
Мразя да мразя ...


Вто Юни 25, 2019 6:27 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Фев 26, 2006 5:52 pm
Мнения: 10356
Местоположение: Добрич
Мнение Re: JSON Parser
-fstack_usage показва само локалната функция, без да брои консумацията на виканите... Поне така се държеше последно като го тествах.

Дискутирали сме го и преди, че не е голяма философия да се напише тулче, което да проследява виканията и да смята. Проблемите са в асемблерски функция, калбаци и виртуални++. Но не са чак толкова голям проблем, асемблера си има директиви за стекa и аз обикновено ги ползвам щото иначе stack unwinding-a много се шашка. А ако има липсващи то спокойно може да изкара warning и да ги прескочи. За виртуалните функции няма нужда да се опитва да отгатва, достатъчно е да вземе максималния юсидж от всички наследници. С калбаците единствено е по-сложно... но то е проблем за тия дето ги ползват, аз проблем нямам ;-)


Вто Юни 25, 2019 8:11 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 3855
Местоположение: Габрово
Мнение Re: JSON Parser
Чибито ползват същия подход да проверяват при context switch:
http://chibios.org/dokuwiki/doku.php?id=chibios:kb:stacks
Това не виждам как ще помогне ако в определен нишка някой добави хубава локален масив от 4К. Което си е негова грешка, това добре, Кофтито е ако този някой в тази нишка не е пипал нищо, но някой някъде в някаква библиотека е променил функция, която тази нишка вика, и онази външна функция е решила да дърпа много стек. Това без някакъв анализ на възможния call chain няма как да се хване.
Имам някакви спомени че каил-а за 8051 правеше подобни анализи и даже гърмеше с грешка ако имаш неизползвани функции. Май се опитваше да предполага и стека, ама то там заради архитектурата му трябва. Което обаче не значи че не е по силите на компилатора.


Вто Юни 25, 2019 8:18 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: JSON Parser
Друго имах в предвид - компилаторът може да слага код в пролога на всяка функция за проверка или алокиране на стека - например да вика някаква функция, която си е наясно с заделеният стек за текущата нишка и проверява дали ще се омаже нещо още преди да е омазано ... това ще вкара малко овърхед но пък гарантирано ще хване всички препълвания за разлика от ползването на маркери на дъното на стека.

_________________
Мразя да мразя ...


Вто Юни 25, 2019 9:06 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Фев 26, 2006 5:52 pm
Мнения: 10356
Местоположение: Добрич
Мнение Re: JSON Parser
palavrov написа:
Друго имах в предвид - компилаторът може да слага код в пролога на всяка функция за проверка или алокиране на стека - например да вика някаква функция, която си е наясно с заделеният стек за текущата нишка и проверява дали ще се омаже нещо още преди да е омазано ... това ще вкара малко овърхед но пък гарантирано ще хване всички препълвания за разлика от ползването на маркери на дъното на стека.


Може да се направи... при мен даже е супер лесно, тъй като обикновено резервирам CPU регистър като указател към текущата нишка, съответно това е указател към TCB-то. Стек поинтера също естествено е два указателя, така че овърхеда ще е всичко на всичко две инструкции - едно сравнение на регистри и един преход, който нормално няма да се изпълнява.
Има и много други решения, примерно тая проверка може да се прави при смяна на контекста, вместо във всяка функция. Както чиби-то. Някои пък ползват и MPU, което пък не чака да се стига до мазане изобщо. Въобще решения има. Въпросът е, че и простото разполагане на стек/ТСВ върши достатъчна работа и не ми се е налагало да правя други капани. Пак казвам проблемът не е как да разбера за белята след като е станала. Тя стане ли, аз разбирам по един или друг начин ;-) Въпросът е да не се стига нито до бели нито до преразход на памет. Демек номерът е нещо да смята колко точно стек е нужен и да го сетва и да не стига до бели.


Вто Юни 25, 2019 9:39 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: JSON Parser
Е, с рекурсивен парсер няма как да го сметнеш - всичко зависи от входяшите данни.

Но пък в този случай можеш да избягаш от рекурсиите и динамичното алокиране с пресмятане наново на всичкото това което иначе би запомнил. И то това е по скоро чисто теоретичен проблем който на практика да го няма - повечето json файлове се ползват колкото за конфигуриране на параметри и не са въобще навложени на повече от 1-2 нива.

_________________
Мразя да мразя ...


Вто Юни 25, 2019 11:08 am
Профил
Покажи мненията от миналия:  Сортирай по  
Отговори на тема   [ 37 мнения ]  Отиди на страница Предишна  1, 2, 3  Следваща

Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 7 госта


Вие не можете да пускате нови теми
Вие не можете да отговаряте на теми
Вие не можете да променяте собственото си мнение
Вие не можете да изтривате собствените си мнения
Вие не можете да прикачвате файл

Търсене:
Иди на:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.
Хостинг и Домейни