[ClusterLabs Developers] Pacemaker
Владимир Лямин
st067898 at student.spbu.ru
Sat Jan 7 15:41:41 EST 2023
Hello, I'm Lyamin Vladimir. First-year master of St. Petersburg State
University. I decided to optimize the running time of the
pcmk__unpack_constraints function, since there is a loop over all the data
here. I decided to use a hash table to optimize this.
A hash table structure has been added, as well as functions to manage it.
pe_resource_t* compareKey(const char* key, struct set *array);
int getHash(const char *S);
void push(Node **head, pe_resource_t* data);
void insert(char* key, pe_resource_t* data, struct set *array);
void init_array(struct set **array);
void insert_children(pe_resource_t * rsc, struct set *hashTable);
Existing functions have also been changed: pcmk__unpack_constraints
(initialization of the hash table) and pcmk__find_constraint_resource
(search for the desired resource)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.clusterlabs.org/pipermail/developers/attachments/20230107/1c118f58/attachment-0001.htm>
-------------- next part --------------
/*
* Copyright 2004-2021 the Pacemaker project contributors
*
* The version control history for this file may have further details.
*
* This source code is licensed under the GNU General Public License version 2
* or later (GPLv2+) WITHOUT ANY WARRANTY.
*/
#include <crm_internal.h>
#include <sys/param.h>
#include <sys/types.h>
#include <stdbool.h>
#include <regex.h>
#include <glib.h>
#include <crm/crm.h>
#include <crm/cib.h>
#include <crm/msg_xml.h>
#include <crm/common/xml.h>
#include <crm/common/xml_internal.h>
#include <crm/common/iso8601.h>
#include <crm/pengine/status.h>
#include <crm/pengine/internal.h>
#include <crm/pengine/rules.h>
#include <pacemaker-internal.h>
#include "libpacemaker_private.h"
#include <stdio.h>
typedef struct Node {
pe_resource_t* value;
struct Node *next;
} Node;
struct set
{
int key;
Node* head;
};
int capacity = 200;
struct set *hashTable = NULL;
pe_resource_t *
compareKey(const char* key, struct set *array);
int
getHash(const char *S);
void
push(Node **head, pe_resource_t* data);
void
insert(char* key, pe_resource_t* data, struct set *array);
void
init_array(struct set **array);
void
free_item(Node *item);
void
free_table(struct set *array);
void
insert_children(pe_resource_t * rsc, struct set *hashTable);
static bool
evaluate_lifetime(xmlNode *lifetime, pe_working_set_t *data_set)
{
bool result = FALSE;
crm_time_t *next_change = crm_time_new_undefined();
result = pe_evaluate_rules(lifetime, NULL, data_set->now, next_change);
if (crm_time_is_defined(next_change)) {
time_t recheck = (time_t) crm_time_get_seconds_since_epoch(next_change);
pe__update_recheck_time(recheck, data_set);
}
crm_time_free(next_change);
return result;
}
void
push(Node **head, pe_resource_t* data) {
Node *tmp = (Node *) malloc(sizeof(Node));
tmp->value = data;
tmp->next = (*head);
(*head) = tmp;
}
int
getHash(const char *S)
{
int i = 0;
int r = 0;
while(*S)
{
i++;
r+=(int)(*S);
S = S + 3;
}
return r % capacity;
}
void
init_array(struct set **array)
{
struct set *tmp = (struct set *) malloc(capacity * sizeof(struct set));
for (int i = 0; i < capacity; i++)
{
tmp[i].key = i;
tmp[i].head = NULL;
}
(*array) = tmp;
}
void
free_item(Node *item) {
free(item);
}
void
free_table(struct set *array) {
for (int i=0; i <capacity; i++) {
Node *item = array[i].head;
while (item != NULL) {
Node *tmp = item->next;
free_item(item);
item = tmp;
}
}
free(array);
}
void
insert(char* key, pe_resource_t* data, struct set *array)
{
int index = getHash(key);
if (array[index].head == NULL)
{
Node *head = NULL;
array[index].key = index;
push(&head, data);
array[index].head = head;
}
else if (array[index].key == index)
{
push(&array[index].head, data);
}
}
pe_resource_t *
compareKey(const char* key, struct set *array)
{
int index = getHash(key);
if (array[index].head == 0)
{
printf("\n Key do not exists \n");
}
else
{
Node *ptr = array[index].head;
while (ptr != NULL)
{
if (!strcmp(key, ptr->value->id)) {
return ptr->value;
}
ptr = ptr->next;
}
return NULL;
}
return NULL;
}
void
insert_children(pe_resource_t * rsc, struct set *hashTable) {
for (GList *gIter = rsc->children; gIter != NULL; gIter = gIter->next) {
pe_resource_t *child = (pe_resource_t *) gIter->data;
insert(child->id, child, hashTable);
insert_children(child, hashTable);
}
}
/*!
* \internal
* \brief Unpack constraints from XML
*
* Given a cluster working set, unpack all constraints from its input XML into
* data structures.
*
* \param[in,out] data_set Cluster working set
*/
void
pcmk__unpack_constraints(pe_working_set_t *data_set)
{
xmlNode *xml_constraints = pcmk_find_cib_element(data_set->input,
XML_CIB_TAG_CONSTRAINTS);
GList *rIter = NULL;
init_array(&hashTable);
for (rIter = data_set->resources; rIter; rIter = rIter->next) {
pe_resource_t *parent = rIter->data;
insert(parent->id, parent, hashTable);
insert_children(parent, hashTable);
}
for (xmlNode *xml_obj = pcmk__xe_first_child(xml_constraints);
xml_obj != NULL; xml_obj = pcmk__xe_next(xml_obj)) {
xmlNode *lifetime = NULL;
const char *id = crm_element_value(xml_obj, XML_ATTR_ID);
const char *tag = crm_element_name(xml_obj);
if (id == NULL) {
pcmk__config_err("Ignoring <%s> constraint without "
XML_ATTR_ID, tag);
continue;
}
crm_trace("Unpacking %s constraint '%s'", tag, id);
lifetime = first_named_child(xml_obj, "lifetime");
if (lifetime != NULL) {
pcmk__config_warn("Support for 'lifetime' attribute (in %s) is "
"deprecated (the rules it contains should "
"instead be direct descendents of the "
"constraint object)", id);
}
if ((lifetime != NULL) && !evaluate_lifetime(lifetime, data_set)) {
crm_info("Constraint %s %s is not active", tag, id);
} else if (pcmk__str_eq(XML_CONS_TAG_RSC_ORDER, tag, pcmk__str_casei)) {
pcmk__unpack_ordering(xml_obj, data_set);
} else if (pcmk__str_eq(XML_CONS_TAG_RSC_DEPEND, tag, pcmk__str_casei)) {
pcmk__unpack_colocation(xml_obj, data_set);
} else if (pcmk__str_eq(XML_CONS_TAG_RSC_LOCATION, tag, pcmk__str_casei)) {
pcmk__unpack_location(xml_obj, data_set);
} else if (pcmk__str_eq(XML_CONS_TAG_RSC_TICKET, tag, pcmk__str_casei)) {
pcmk__unpack_rsc_ticket(xml_obj, data_set);
} else {
pe_err("Unsupported constraint type: %s", tag);
}
}
free_table(hashTable);
}
pe_resource_t *
pcmk__find_constraint_resource(GList *rsc_list, const char *id)
{
pe_resource_t *match = compareKey(id, hashTable);
if(!pcmk__str_eq(match->id, id, pcmk__str_casei)) {
/* We found an instance of a clone instead */
match = uber_parent(match);
crm_debug("Found %s for %s", match->id, id);
}
return match;
}
/*!
* \internal
* \brief Check whether an ID references a resource tag
*
* \param[in] data_set Cluster working set
* \param[in] id Tag ID to search for
* \param[out] tag Where to store tag, if found
*
* \return true if ID refers to a tagged resource or resource set template,
* otherwise false
*/
static bool
find_constraint_tag(pe_working_set_t *data_set, const char *id, pe_tag_t **tag)
{
*tag = NULL;
// Check whether id refers to a resource set template
if (g_hash_table_lookup_extended(data_set->template_rsc_sets, id,
NULL, (gpointer *) tag)) {
if (*tag == NULL) {
crm_warn("No resource is derived from template '%s'", id);
return false;
}
return true;
}
// If not, check whether id refers to a tag
if (g_hash_table_lookup_extended(data_set->tags, id,
NULL, (gpointer *) tag)) {
if (*tag == NULL) {
crm_warn("No resource is tagged with '%s'", id);
return false;
}
return true;
}
crm_warn("No template or tag named '%s'", id);
return false;
}
/*!
* \brief
* \internal Check whether an ID refers to a valid resource or tag
*
* \param[in] data_set Cluster working set
* \param[in] id ID to search for
* \param[out] rsc Where to store resource, if found (or NULL to skip
* searching resources)
* \param[out] tag Where to store tag, if found (or NULL to skip searching
* tags)
*
* \return true if id refers to a resource (possibly indirectly via a tag)
*/
bool
pcmk__valid_resource_or_tag(pe_working_set_t *data_set, const char *id,
pe_resource_t **rsc, pe_tag_t **tag)
{
if (rsc != NULL) {
*rsc = pcmk__find_constraint_resource(data_set->resources, id);
if (*rsc != NULL) {
return true;
}
}
if ((tag != NULL) && find_constraint_tag(data_set, id, tag)) {
return true;
}
return false;
}
/*!
* \internal
* \brief Replace any resource tags with equivalent resource_ref entries
*
* If a given constraint has resource sets, check each set for resource_ref
* entries that list tags rather than resource IDs, and replace any found with
* resource_ref entries for the corresponding resource IDs.
*
* \param[in] xml_obj Constraint XML
* \param[in] data_set Cluster working set
*
* \return Equivalent XML with resource tags replaced (or NULL if none)
* \note It is the caller's responsibility to free the result with free_xml().
*/
xmlNode *
pcmk__expand_tags_in_sets(xmlNode *xml_obj, pe_working_set_t *data_set)
{
xmlNode *new_xml = NULL;
bool any_refs = false;
// Short-circuit if there are no sets
if (first_named_child(xml_obj, XML_CONS_TAG_RSC_SET) == NULL) {
return NULL;
}
new_xml = copy_xml(xml_obj);
for (xmlNode *set = first_named_child(new_xml, XML_CONS_TAG_RSC_SET);
set != NULL; set = crm_next_same_xml(set)) {
GList *tag_refs = NULL;
GList *gIter = NULL;
for (xmlNode *xml_rsc = first_named_child(set, XML_TAG_RESOURCE_REF);
xml_rsc != NULL; xml_rsc = crm_next_same_xml(xml_rsc)) {
pe_resource_t *rsc = NULL;
pe_tag_t *tag = NULL;
if (!pcmk__valid_resource_or_tag(data_set, ID(xml_rsc), &rsc,
&tag)) {
pcmk__config_err("Ignoring resource sets for constraint '%s' "
"because '%s' is not a valid resource or tag",
ID(xml_obj), ID(xml_rsc));
free_xml(new_xml);
return NULL;
} else if (rsc) {
continue;
} else if (tag) {
/* The resource_ref under the resource_set references a template/tag */
xmlNode *last_ref = xml_rsc;
/* A sample:
Original XML:
<resource_set id="tag1-colocation-0" sequential="true">
<resource_ref id="rsc1"/>
<resource_ref id="tag1"/>
<resource_ref id="rsc4"/>
</resource_set>
Now we are appending rsc2 and rsc3 which are tagged with tag1 right after it:
<resource_set id="tag1-colocation-0" sequential="true">
<resource_ref id="rsc1"/>
<resource_ref id="tag1"/>
<resource_ref id="rsc2"/>
<resource_ref id="rsc3"/>
<resource_ref id="rsc4"/>
</resource_set>
*/
for (gIter = tag->refs; gIter != NULL; gIter = gIter->next) {
const char *obj_ref = (const char *) gIter->data;
xmlNode *new_rsc_ref = NULL;
new_rsc_ref = xmlNewDocRawNode(getDocPtr(set), NULL,
(pcmkXmlStr) XML_TAG_RESOURCE_REF, NULL);
crm_xml_add(new_rsc_ref, XML_ATTR_ID, obj_ref);
xmlAddNextSibling(last_ref, new_rsc_ref);
last_ref = new_rsc_ref;
}
any_refs = true;
/* Freeing the resource_ref now would break the XML child
* iteration, so just remember it for freeing later.
*/
tag_refs = g_list_append(tag_refs, xml_rsc);
}
}
/* Now free '<resource_ref id="tag1"/>', and finally get:
<resource_set id="tag1-colocation-0" sequential="true">
<resource_ref id="rsc1"/>
<resource_ref id="rsc2"/>
<resource_ref id="rsc3"/>
<resource_ref id="rsc4"/>
</resource_set>
*/
for (gIter = tag_refs; gIter != NULL; gIter = gIter->next) {
xmlNode *tag_ref = gIter->data;
free_xml(tag_ref);
}
g_list_free(tag_refs);
}
if (!any_refs) {
free_xml(new_xml);
new_xml = NULL;
}
return new_xml;
}
/*!
* \internal
* \brief Convert a tag into a resource set of tagged resources
*
* \param[in] xml_obj Constraint XML
* \param[out] rsc_set Where to store resource set XML created based on tag
* \param[in] attr Name of XML attribute containing resource or tag ID
* \param[in] convert_rsc Convert to set even if \p attr references a resource
* \param[in] data_set Cluster working set
*/
bool
pcmk__tag_to_set(xmlNode *xml_obj, xmlNode **rsc_set, const char *attr,
bool convert_rsc, pe_working_set_t *data_set)
{
const char *cons_id = NULL;
const char *id = NULL;
pe_resource_t *rsc = NULL;
pe_tag_t *tag = NULL;
*rsc_set = NULL;
CRM_CHECK((xml_obj != NULL) && (attr != NULL), return false);
cons_id = ID(xml_obj);
if (cons_id == NULL) {
pcmk__config_err("Ignoring <%s> constraint without " XML_ATTR_ID,
crm_element_name(xml_obj));
return false;
}
id = crm_element_value(xml_obj, attr);
if (id == NULL) {
return true;
}
if (!pcmk__valid_resource_or_tag(data_set, id, &rsc, &tag)) {
pcmk__config_err("Ignoring constraint '%s' because '%s' is not a "
"valid resource or tag", cons_id, id);
return false;
} else if (tag) {
GList *gIter = NULL;
/* A template/tag is referenced by the "attr" attribute (first, then, rsc or with-rsc).
Add the template/tag's corresponding "resource_set" which contains the resources derived
from it or tagged with it under the constraint. */
*rsc_set = create_xml_node(xml_obj, XML_CONS_TAG_RSC_SET);
crm_xml_add(*rsc_set, XML_ATTR_ID, id);
for (gIter = tag->refs; gIter != NULL; gIter = gIter->next) {
const char *obj_ref = (const char *) gIter->data;
xmlNode *rsc_ref = NULL;
rsc_ref = create_xml_node(*rsc_set, XML_TAG_RESOURCE_REF);
crm_xml_add(rsc_ref, XML_ATTR_ID, obj_ref);
}
/* Set sequential="false" for the resource_set */
pcmk__xe_set_bool_attr(*rsc_set, "sequential", false);
} else if ((rsc != NULL) && convert_rsc) {
/* Even a regular resource is referenced by "attr", convert it into a resource_set.
Because the other side of the constraint could be a template/tag reference. */
xmlNode *rsc_ref = NULL;
*rsc_set = create_xml_node(xml_obj, XML_CONS_TAG_RSC_SET);
crm_xml_add(*rsc_set, XML_ATTR_ID, id);
rsc_ref = create_xml_node(*rsc_set, XML_TAG_RESOURCE_REF);
crm_xml_add(rsc_ref, XML_ATTR_ID, id);
} else {
return true;
}
/* Remove the "attr" attribute referencing the template/tag */
if (*rsc_set != NULL) {
xml_remove_prop(xml_obj, attr);
}
return true;
}
/*!
* \internal
* \brief Create constraints inherent to resource types
*
* \param[in,out] data_set Cluster working set
*/
void
pcmk__create_internal_constraints(pe_working_set_t *data_set)
{
crm_trace("Create internal constraints");
for (GList *iter = data_set->resources; iter != NULL; iter = iter->next) {
pe_resource_t *rsc = (pe_resource_t *) iter->data;
rsc->cmds->internal_constraints(rsc);
}
}
More information about the Developers
mailing list